The only known compound of sodium and hydrogen is archetypal ionic NaH. Application of high pressure is known to promote states with higher atomic coordination, but extensive searches for polyhydrides with unusual stoichiometry have had only limited success in spite of several theoretical predictions. Here we report the first observation of the formation of polyhydrides of Na (NaH3 and NaH7) above 40 GPa and 2,000 K. We combine synchrotron X-ray diffraction and Raman spectroscopy in a laser-heated diamond anvil cell and theoretical random structure searching, which both agree on the stable structures and compositions. Our results support the formation of multicenter bonding in a material with unusual stoichiometry. These results are applicable to the design of new energetic solids and high-temperature superconductors based on hydrogen-rich materials.