Sodium chloride (NaCl) plays an important role in geochemistry, biology, industry, and food production, and it is among the most common salts in the solar system. Here, we report the discovery of a metastable NaCl dihydrate formed through rapid freezing (10¹–10² K s^–1) of a NaCl solution at ambient pressure. Using synchrotron X-ray and neutron powder diffraction, we show that it transforms irreversibly to hydrohalite and ice Ih above 190 K upon heating and propose it is structurally related to hydrohalite with a 3 × 1 × 3 supercell as its unit cell. Calorimetric analyses reveal that the new hydrate transforms to hydrohalite with a heat release of −3.47 ± 0.55 kJ mol^–1. The identification of this new NaCl dihydrate on the surfaces of icy worlds such as the moons of Jupiter and Saturn could indicate regions of recent activity where subsurface brines have frozen rapidly, priority targets for upcoming planetary missions.