Hydrated evaporite minerals have the ability to hold large amounts of H2O, making them a potential source of H2O in cold, low-PH2O environments such as the surface of Mars. Many of these hydrated evaporite minerals experience a reversible change in hydration state in response to changes in temperature (T) and relative humidity (RH). Such phases may thus have the potential to interact with the martian atmosphere on a daily or seasonal basis. The Na2Mg(SO4)2·nH2O system was previously thought to contain three hydrated phases: a decahydrate (n = 10), konyaite (n = 5), and blödite (n = 4). We examined this system using temperature- and RH-controlled X-ray powder diffraction (XRD) methods, as well as temperature-controlled single-crystal X-ray diffraction. When blödite was exposed to sub-freezing conditions, T ≤ −10 °C, a new phase was produced (n = 16, 52 wt%H2O). Similar low-temperature behavior has been documented in the MgSO4·nH2O system, through the presence of meridianiite (Peterson et al. 2007). The hydration and dehydration behavior of phases in the Na2Mg(SO4)2·nH2O system was evaluated with powder XRD from −30 to >25 °C and from ~99 to near 0% RH, and single-crystal XRD data were collected for the n = 16 phase at −120 °C. The 16-hydrate is triclinic, space group P1̄, with unit-cell parameters a = 6.5590(12), b = 6.6277(14), c = 14.441(3) Å, α = 87.456(15)°, β = 79.682(15)°, γ = 65.847(13)°, and a unit-cell volume of 563.3(2) Å3. The existence of this new phase at low temperatures, its high hydration state, and its ability to form reversibly from blödite all suggest that if phases in this system exist on the martian surface, they will participate in the Mars H2O cycle.