Fly Ash Belite Cement (FABC) pastes with and without nanosilica additions have been prepared and maintained in sulfate solutions (Na2SO4 0.5M) for 180 days. The mechanical performance and the changes in microstructure have been monitored at 28, 90, and 180 days by compressive strength, X-ray diffraction (XRD), and 29Si MAS NMR measurements. We have found that, unexpectedly, and contrary to what happens in Ordinary Portland Cements (OPC), the addition of nanosilica particles induces an initial decline in the compressive strength of the samples. Only in samples maintained for a long time (180 days) does the nanosilica addition improve the mechanical properties. Our XRD and 29Si NMR experiments have revealed that although nanosilica additions trigger the consumption of Belite phases, this is not always accompanied by formation of longer calcium–silicate–hydrate (C–S–H) gel structures. Only at a long time (180 days), and due to a mechanism that seems to be controlled by the pH of the samples, do the nanosilica additions lead to high-polymerized C–S–H gels.