Alkali metals exhibit unexpected structures and electronic behavior at high pressures. Compression of metallic sodium (Na) to 200 GPa leads to the stability of a wide-band-gap insulator with the double hexagonal hP4 structure. Post-hP4 structures remain unexplored, but they are important for addressing the question of the pressure at which Na reverts to a metal. Here we report the reentrant metallicity of Na at the very high pressure of 15.5 terapascal (TPa), predicted using first-principles structure searching simulations. Na is therefore insulating over the large pressure range of 0.2-15.5 TPa. Unusually, Na adopts an oP8 structure at pressures of 117-125 GPa, and the same oP8 structure at 1.75-15.5 TPa. Metallization of Na occurs on formation of a stable and striking body-centered cubic cI24 electride structure consisting of Na12 icosahedra, each housing at its center about one electron which is not associated with any Na ions. ; Comment: 5 pages, 4 figures, PRL (2015)