Using density functional molecular dynamics free energy calculations, we show that the body centered cubic (bcc) phase of superionic ice previously believed to be the only phase is, in fact, thermodynamically unstable compared to a novel phase with oxygen positions in face centered cubic lattice sites. The novel phase has a lower proton mobility than the bcc phase and may exhibit a higher melting temperature. We predict a transition between the two phases at a pressure of 1±0.5 Mbar, with potential consequences for the interiors of ice giants such as Uranus and Neptune.