Magnetite, Fe3O4, is the oldest known magnetic mineral and archetypal mixed-valence oxide. Despite its recognized role in deep Earth processes, the behavior of magnetite at extreme high-pressure high-temperature (HPHT) conditions remains insufficiently studied. Here, we report on single-crystal synchrotron X-ray diffraction experiments up to similar to 80 GPa and 5000 K in diamond anvil cells, which reveal two previously unknown Fe3O4 polymorphs, gamma-Fe3O4 with the orthorhombic Yb3S4-type structure and delta-Fe3O4 with the modified Th3P4-type structure. The latter has never been predicted for iron compounds. The decomposition of Fe3O4 at HPHT conditions was found to result in the formation of exotic phases, Fe5O7 and Fe25O32, with complex structures. Crystal-chemical analysis of iron complex Crystal-chemical analysis oxides suggests the high-spin to low-spin crossover in octahedrally coordinated Fe3+ in the pressure interval between 43 and 51 GPa. Our experiments demonstrate that HPHT conditions promote the formation of ferric-rich Fe-O compounds, thus arguing for the possible involvement of magnetite in the deep oxygen cycle.