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 Fe$_2$O$_3$ and FeO$_2$ 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 Fe$_2$O$_3$ with $P2_12_12_1$ symmetry which is found to be more stable than the known Rh$_2$O$_3$(II) phase at pressures above $sim$233 GPa. We also report two new structures of FeO, with $Pnma$ and $Rbar{3}m$ symmetries, which are found to be stable within the ranges 195-285 GPa and 285-500 GPa, respectively, and two new structures of Fe$_3$O$_4$ with $Pca2_1$ and $P2_1/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 Fe$_4$O$_5$ with $P4_2/n$ and $Pbar{3}m1$ symmetries, which are found to be stable within the ranges 100-231 GPa and 231-500 GPa, respectively. Our new structures of Fe$_3$O$_4$ and Fe$_4$O$_5$ are found to have lower enthalpies than their known structures within their respective stable pressure ranges.