Transition metal oxide layers on metal surfaces often show superior catalytic performance as compared to conventional, i.e., metal-on-oxide, systems. In this work, we studied the CO oxidation reaction over FeO supported by Pt(111) and observed strong size effects on the reactivity. The monolayer islands below 5 nm in size showed a light-off temperature for CO2 production 200 K lower than for the 30 nm islands. In an attempt to rationalize the size effect, we have performed oxygen desorption experiments and have combined them with an extended DFT analysis to provide insight into the bonding of various oxygen species in such systems. The theoretical results on isolated FeO2 islands indicate a substantially lower stability of the boundary oxygen atoms as compared with the same islands embedded into an FeO layer in qualitative agreement with experiment showing that the smaller the island, the lower the desorption temperature. To the best of our knowledge, the results demonstrate the first example of a size effect in oxidation catalysis on two-dimensional systems.