We have systematically studied the CO oxidation on various nanosized gold clusters with sizes ranging from 0.3 to 0.8 nm on the basis of density functional theory (DFT) calculations. A hitherto unreported trimolecular Langmuir-Hinshelwood (LH) mechanism is proposed, which offers new insights into the fundamental mechanism for CO oxidation on nanosized gold clusters. Specifically, we find that the coadsorbed CO molecule at a unique triangular Au-3 active site can act as a promoter for the scission of an O-O bond, leading to the spontaneous formation (due to extremely low energy barrier) of two CO2 molecules as product. The key step to the O-O bond scission in the OCOO* intermediate is significantly accelerated due to the electrophilic attack of the coadsorbed neighboring CO molecule on the triangular Au3 site. This new mechanism is called CO self-promoting oxidation, which can be visualized in real time from the trajectory of a Born Oppenheimer molecular dynamics (BOMD) simulation. We also find that such CO self-promoting oxidation is quite universal, as long as the triangular Au3 reaction site is available. This is demonstrated in two prototype metal oxide supported gold nanostructure systems: namely, Au-n/MgO and bilayer-Au/TiO2. The coadsorbed CO can not only serve as a promoter for its own oxidation but also promote other oxidation reactions such as styrene oxidation through expediting O-O scission on gold nanostructures.