Iron oxides play an increasingly prominent role in heterogeneous catalysis, hydrogen production, spintronics and drug delivery. The surface or material interface can be performance limiting in these applications, so it is vital to determine accurate atomic-scale structures for iron oxides and understand why they form. Using a combination of quantitative low-energy electron diffraction, scanning tunneling microscopy, and density functional theory calculations, we show that an ordered array of subsurface iron vacancies and interstitials underlies the well-known (rt2xrt2)R45{deg} reconstruction of Fe3O4(001). This hitherto unobserved stabilization mechanism occurs because the iron oxides prefer to redistribute cations in the lattice in response to oxidizing or reducing environments. Many other metal oxides also achieve stoichiometric variation in this way, so such surface structures are likely commonplace.