Porous building materials are very susceptible to the aggressive action of salts, sodium sulfate being one of the most damaging. Laboratory and field experiments show that the intensity of damage depends on the structure of the porous material, as well as the type and amount of salt. In this paper we investigate the nucleation process of sodium sulfate on two kinds of substrates: calcite and quartz particles, the main components of calcitic and quartzitic stones, respectively, to assess the influence of the substrate chemistry on the crystalline phase being formed and on the nucleation process. Nuclear Magnetic Resonance (NMR) is used to investigate the cooling-induced crystallization of sodium sulfate in mixtures of solution with different amounts of substrate particles. Temperature and concentration are measured by NMR and used to calculate the crystallization rate. The phase that precipitates is the metastable heptahydrate. Our experiments show that nucleation is energetically more favorable on a calcitic substrate; that is, the required supersaturation is lower than on the quartzitic substrate. Under isothermal conditions, the precipitation rate is faster in the presence of calcite than quartz.