Very active FeOx-Au catalysts for CO oxidation are obtained after depositing nanoparticles of FeO, Fe3O4, and Fe2O3 on a Au(111) substrate. Neither FeO nor Fe2O3 is stable under the reaction conditions. Under an environment of CO/O2, they undergo oxidation (FeO) or reduction (Fe2O3) to yield nanoparticles of Fe3O4 that are not formed in a bulk phase. Using a combined experimental and theoretical approach, we show a strong oxide-metal interaction (SOMI) between Fe3O4 nanostructures and Au(111), which gives the oxide special properties, allows the formation of an active phase, and provides a unique interface to facilitate a catalytic reaction. Our work highlights the important role that the SOMI can play in enhancing the catalytic performance of the oxide component in metal-oxide catalysts.