Predicting and controlling nanostructure formation during nucleation can pave the way to synthesizing novel energy materials via crystallization. However, such control over nucleation and crystallization remains challenging due to an inadequate understanding of critical factors that govern evolving atomistic structures and dynamics. Herein, we utilize coordination number as a reaction coordinate and rate theory to investigate how sodium sulfate, commonly known as a phase-change energy material, nucleates in a supersaturated aqueous solution. In conjunction with ab initio and force field-based molecular dynamics simulation, the rate theoretical analysis reveals that sodium sulfate from an initially dissolved metastable state transits to a heterogeneous mixture of prenucleated clusters and finally to a large cylindrical zigzag morphology. Measurements of Raman spectra and their ab initio modeling confirm that this nucleated morphology contains a few waters for every sulfate. Rate processes such as solvent exchange and desolvation exhibit high sensitivity to the evolving prenucleation/nucleation structures, providing a means to distinguish between critical nucleation precursors. Desolvation and forming the first-shell interionic coordination structure via monomer-by-monomer addition around sulfates are found to explain the formation of large nuclei. Thus, a detailed understanding of the step-by-step structure formation across scales has been achieved. This can be leveraged to predict nucleation-related structures and dynamics and potentially control the synthesis of novel phase-change materials for energy applications.