Adopting low-index single-crystal surfaces as models for metal nanoparticle catalysts has been questioned by the experimental findings of adsorbate-induced formation of subnanometer clusters on several single-crystal surfaces. We used density functional theory calculations to elucidate the conditions that lead to cluster formation and show how adatom formation energies enable efficient screening of the conditions required for adsorbate-induced cluster formation. We studied a combination of eight face-centered cubic transition metals and 18 common surface intermediates and identified systems relevant to catalytic reactions, such as carbon monoxide (CO) oxidation and ammonia (NH3) oxidation. We used kinetic Monte Carlo simulations to elucidate the CO-induced cluster formation process on a copper surface. Scanning tunneling microscopy of CO on a nickel (111) surface that contains steps and dislocations points to the structure sensitivity of this phenomenon. Metal-metal bond breaking that leads to the evolution of catalyst structures under realistic reaction conditions occurs much more broadly than previously thought.