We investigate the high-pressure phase diagram of the hydrous mineral brucite, Mg(OH)2, using structure search algorithms and ab initio simulations. We predict a high-pressure phase stable at pressure and temperature conditions found in cold subducting slabs in Earth’s mantle transition zone and lower mantle. This prediction implies that brucite can play a much more important role in water transport and storage in Earth’s interior than hitherto thought. The predicted high-pressure phase, stable in calculations between 20 and 35 GPa and up to 800 K, features MgO6 octahedral units arranged in the anatase–TiO2 structure. Our findings suggest that brucite will transform from a layered to a compact 3D network structure before eventual decomposition into periclase and ice. We show that the high-pressure phase has unique spectroscopic fingerprints that should allow for straightforward detection in experiments. The phase also has distinct elastic properties that might make its direct detection in the deep Earth possible with geophysical methods.