Using density functional molecular dynamics free energy calculations, we show that the body-centered-cubic 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 fcc lattice sites. The novel phase has a lower proton mobility than the bc 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.