In this first-principles study we evaluate the thermodynamic and kinetic stability of Rh and Pt single-atoms (SAs) and subnano clusters on the monoclinic zirconia surface with and without a CO atmosphere. To address the kinetic stability and agglomeration of SAs to clusters and nanoparticles, a non-equilibrium nanothermodynamic approach is developed and parametrised using data computed with density functional theory. The bare subnano clusters are more stable than SA and become more so with increasing size, which means the agglomeration is always favoured. CO binds strongly to the single atoms and clusters, and our atomistic thermodynamics treatment indicates that some CO will be present even at ultra-high vacuum conditions. A CO atmosphere is shown to hinder cluster growth from SA, and is even capable of spontaneous cluster disintegration in the case of Pt clusters. Analysis of the CO stretching frequencies reveals that subnano clusters and single atoms should give peaks in the same region, and that using them to distinguish between surface species requires caution.