We present results of ab initio electronic structure and molecular dynamics simulations (AIMD), as well as a microkinetic model of CO oxidation catalyzed by TiO2 supported Au nanocatalysts. A coverage-dependent microkinetic analysis, based on energetics obtained with density functional methods, shows that the dominant kinetic pathway, activated oxygen species, and catalytic active sites are all strongly depended on both temperature and oxygen partial pressure. Under oxidizing conditions and T < 400 K, the prevalent pathway involves a dynamic single atom catalytic mechanism. This reaction is catalyzed by a transient Au-CO species that migrates from the Au-cluster onto a surface oxygen adatom. It subsequently reacts with the TiO2 support via a Mars van Krevelen mechanism to form CO2 and finally the Au atom reintegrates back into the gold cluster to complete the catalytic cycle. At 300 ≤ T ≤ 600 K, oxygen-bound single Oad-Au(+)-CO sites and the perimeter Au-sites of the nanoparticle work in tandem to optimally catalyze the reaction. Above 600 K, a variety of alternate pathways associated with both single-atom and the perimeter sites of the Au nanoparticle are found to be active. Under low oxygen pressures, Oad-Au(+)-CO species can be a source of catalyst deactivation and the dominant pathway involves only Au-perimeter sites. A detailed comparison of the current model and the existing literature resolves many apparent inconsistencies in the mechanistic interpretations.