Heterogeneous single-atom catalysts involve isolated metal atoms anchored to a support, displaying high catalytic performance and stability in many important chemical reactions. We present a general theoretical framework to establish the thermodynamic stability of metal single atoms and metal nanoparticles on a support in the presence of adsorbates. As a case study, we establish for Pt-CeO 2 the CO partial pressure and temperature range within which Pt single atoms are more stable than Pt nanoparticles. Density functional theory and kinetic Monte Carlo simulations demonstrate that Pt atoms doped into the CeO 2 surface exhibit a very high CO oxidation activity and thermodynamic stability in comparison to models involving Pt single atoms on terraces and steps of CeO 2 . An intermediate CO adsorption strength is important to explain a high activity. Our work provides a systematic strategy to evaluate the stability and reactivity of single atoms on a support.