Finely dispersed nanometre-scale gold particles are known to catalyse several oxidation reactions in aerobic, ambient conditions. The catalytic activity has been explained by various complementary mechanisms, including support effects, particle-size-dependent metal-insulator transition, charging effects, frontier orbital interactions and geometric fluxionality. We show, by considering a series of robust and structurally well-characterized ligand-protected gold clusters with diameters between 1.2 and 2.4 nm, that electronic quantum size effects, particularly the magnitude of the so-called HOMO-LUMO energy gap, has a decisive role in binding oxygen to the nano-catalyst in an activated form. This can lead to the oxidation reaction 2CO + O(2) → 2CO(2) with low activation barriers. Binding of dioxygen is significant only for the smallest particles with a metal core diameter clearly below 2 nm. Our results suggest a potentially viable route to practical applications using ligand-protected gold clusters for green chemistry.