In exsolution, nanoparticles form by emerging from oxide hosts by application of redox driving forces, leading to transformative advances in stability, activity, and efficiency over deposition techniques, and resulting in a wide range of new opportunities for catalytic, energy and net-zero-related technologies. However, the mechanism of exsolved nanoparticle nucleation and perovskite structural evolution, has, to date, remained unclear. Herein, we shed light on this elusive process by following in real time Ir nanoparticle emergence from a SrTiO3 host oxide lattice, using in situ high-resolution electron microscopy in combination with computational simulations and machine learning analytics. We show that nucleation occurs via atom clustering, in tandem with host evolution, revealing the participation of surface defects and host lattice restructuring in trapping Ir atoms to initiate nanoparticle formation and growth. These insights provide a theoretical platform and practical recommendations to further the development of highly functional and broadly applicable exsolvable materials.