The distribution, accumulation and circulation of oxygen and hydrogen in Earth's interior dictate the geochemical evolution of the hydrosphere, atmosphere and biosphere. The oxygen-rich atmosphere and iron-rich core represent two end-members of the oxygen-iron (O-Fe) system, overlapping with the entire pressure-temperature-composition range of the planet. The extreme pressure and temperature conditions of the deep interior alter the oxidation states, spin states and phase stabilities of iron oxides, creating new stoichiometries, such as Fe4O5 (ref. 5) and Fe5O6 (ref. 6). Such interactions between O and Fe dictate Earth's formation, the separation of the core and mantle, and the evolution of the atmosphere. Iron, in its multiple oxidation states, controls the oxygen fugacity and oxygen budget, with hydrogen having a key role in the reaction of Fe and O (causing iron to rust in humid air). Here we use first-principles calculations and experiments to identify a highly stable, pyrite-structured iron oxide (FeO2) at 76 gigapascals and 1,800 kelvin that holds an excessive amount of oxygen. We show that the mineral goethite, FeOOH, which exists ubiquitously as 'rust' and is concentrated in bog iron ore, decomposes under the deep lower-mantle conditions to form FeO2 and release H2. The reaction could cause accumulation of the heavy FeO2-bearing patches in the deep lower mantle, upward migration of hydrogen, and separation of the oxygen and hydrogen cycles. This process provides an alternative interpretation for the origin of seismic and geochemical anomalies in the deep lower mantle, as well as a sporadic O2 source for the Great Oxidation Event over two billion years ago that created the present oxygen-rich atmosphere.