The ex-solution process, in which metal nanoparticles are grown on a host oxide, can be used to synthesize nanocatalysts with excellent thermal and chemical durability via spontaneous heterogeneous nucleation. However, this technique lacks a means to control the particle size and density because the amounts of ex-solved metal elements vary with the reduction conditions. Here, we devise a strategy to achieve small particle sizes and high particle densities concurrently by controlling the temperature (T), oxygen partial pressure (pO(2)) and ramping rate of the temperature. Quantitative analyses of Co particles ex-solved on Sr0.98Ti0.95Co0.05O3-delta thin films using ex situ SEM and in situ TEM reveal that the increasing T and decreasing the pO(2) lead to smaller particle sizes with higher density levels and vice versa, contrary to common ex-solution examples. We find that nucleation thermodynamics dictates such counterintuitive behaviors of particle characteristics, which are attributed to our specific ex-solution conditions in which particle interactions are minimized and all the Co atoms are ex-solved under highly reducible conditions. We also demonstrated the feasibility of our strategy via CO oxidation with typical powder-based catalysts, suggesting that this method can be extended to various chemical/electrochemical applications.