Supported gold nanoparticles have excited much interest owing to their unusual and somewhat unexpected catalytic properties1, 2, 3, 4, 5, 6, 7, but the origin of the catalytic activity is still not fully understood. Experimental work4 on gold particles supported on a titanium dioxide (110) single-crystal surface has established a striking size threshold effect associated with a metal-to-insulator transition, with gold particles catalytically active only if their diameters fall below 3.5 nm. However, the remarkable catalytic behaviour might also in part arise from strong electronic interaction between the gold and the titanium dioxide support2, 3, 5. In the case of industrially important selective oxidation reactions, explanation of the effectiveness of gold nanoparticle catalysts is complicated by the need for additives to drive the reaction5, 7, 8, and/or the presence of strong support interactions and incomplete understanding of their possible catalytic role1, 2, 3, 5. Here we show that very small gold entities (1.4 nm) derived from 55-atom gold clusters and supported on inert materials are efficient and robust catalysts for the selective oxidation of styrene by dioxygen. We find a sharp size threshold in catalytic activity, in that particles with diameters of 2 nm and above are completely inactive. Our observations suggest that catalytic activity arises from the altered electronic structure intrinsic to small gold nanoparticles, and that the use of 55-atom gold clusters may prove a viable route to the synthesis of robust gold catalysts suited to practical application.