We have used density-functional-theory methods and the ab initio random structure searching (AIRSS) approach to predict stable structures and stoichiometries of mixtures of iron and oxygen at high pressures. Searching was performed for 12 different stoichiometries at pressures of 100, 350 and 500 GPa, which involved relaxing more than 32 000 structures. We find that Fe2O3 and FeO2 are the only phases stable to decomposition at 100 GPa, while at 350 and 500 GPa several stoichiometries are found to be stable or very nearly stable. We report a new structure of Fe2O3 with P2(1)2(1)2(1)2 symmetry which is found to be more stable than the known Rh2O3(II) phase at pressures above  ∼233 GPa. We also report two new structures of FeO, with Pnma and R3m symmetries, which are found to be stable within the ranges 195-285 GPa and 285-500 GPa, respectively, and two new structures of Fe3O4 with Pca21 and P21/c symmetries, which are found to be stable within the ranges 100-340 GPa and 340-500 GPa, respectively. Finally, we report two new structures of Fe4O5 with P42/n and [Formula: see text] symmetries, which are found to be stable within the ranges 100-231 GPa and 231-500 GPa, respectively. Our new structures of Fe3O4 and Fe4O5 are found to have lower enthalpies than their known structures within their respective stable pressure ranges.