We propose three new phases of H2O under ultrahigh pressure. Our structural search was performed using an adaptive genetic algorithm which allows an extensive exploration of crystal structure. The new sequence of pressure-induced transitions beyond ice X at 0 K should be ice X - Pbcm - Pbca - Pmc21 - P21 - P21/c phases. Across the Pmc21 - P21 transition, the coordination number of oxygen increases from 4 to 5 with a significant increase of density. All stable crystalline phases have nonmetallic band structures up to 7 TPa.