Plane-wave pseudopotential density functional methods using the Perdew-Burke-Ernzerhof exchange-correlation functional were used to investigate theoretically the structures of five NaOH hydrate phases through optimization of lattice parameters and atomic coordinates. Although all the calculations were carried out with P1 symmetry, we find in four of the five cases that the experimentally determined space group is maintained to high accuracy. Particular focus is placed on the coordination environments of Na+ and OH−. The Na-O distances are, in general, overestimated; however, the sodium ion coordination polyhedra are well reproduced by the theoretical calculations, including the fivefold coordinated sodium atom in the α-NaOH·4H2O structure. The theoretical calculations correctly predict that α-NaOH·4H2O is lower in energy than the metastable β-NaOH·4H2O phase; thus, the α phase is stable even in the absence of proton disorder. The octahedral coordination environment around OH− is calculated accurately, including the distances of the weak OH−OH2 hydrogen bonds in which the hydroxide ion acts as the proton donor. This work provides further evidence of the reliability of the Perdew-Burke-Ernzerhof exchange-correlation functional in hydrogen bonded systems, providing a direct, unambiguous test of the elusive hydroxide-water interaction.