A unique phase, belonging to an orthorhombic crystal system (Pbca, Z = 8), is proposed in AlOOH using crystal structure searches based on an evolutionary genetic algorithm method, combined with density functional theory. This phase features a nonlinear asymmetric doubly covalent hydrogen-bond and metal cations that are sixfold oxygen coordinated. Unlike the earlier proposed monoclinic phase, the stability region of Pbca (166–189 GPa) lies well below the pressure of decomposition to Al2O3+ice X (287 GPa). In GaOOH the Pbca-type phase is not energetically favorable at any pressure. In the course of evaluating the breakdown of GaOOH to its constituent oxides, we have found a new phase of Ga2O3 (U2S3-type). In InOOH, Pbca is energetically favorable over a narrow pressure interval (12–17 GPa). Also in InOOH, we find a new tetragonal structure (P421m, Z = 4) stable above 51 GPa. This phase has nonlinear asymmetric hydrogen-bonds and metal cations that are sevenfold oxygen coordinated. Phonon calculations confirm the vibrational stability of the new phases and show that the high-pressure polymorphs of AlOOH are likely to be important carriers of water into the deep lower mantles of Earth and rocky super-Earths.