Heterogeneous catalysis is key for chemical transformations. Understanding how catalyst active sites dynamically evolve at the atomic scale under reaction conditions is a prerequisite for accurate determination of catalytic mechanisms and predictably developing catalysts. We combine in-situ observation and Machine Learning accelerated first-principle atomistic simulations to uncover the mechanism of restructuring for Pt catalysts under a pressure of carbon monoxide CO. We show that a high CO coverage at a Pt step edge triggers the formation of atomic protrusions of low-coordination Pt atoms, that then detach from the step edge to create sub-nano-islands on the terraces, where undercoordinated sites are stabilized by the CO adsorbates. These studies open an avenue to achieve an atom-scale understanding of structural dynamics of more complex metal nanoparticles under reaction.