The first atomistic simulations of the CO-induced lifting of the Pt(100)-hex reconstruction have been performed. During this phase transformation the surface changes back to bulk-terminated Pt(100)-(1×1), whereby the surface atom density decreases by ~20%. The simulations reveal a mechanism collective in nature, indicating that restructuring proceeds through ejection of chains of Pt atoms. These chains explain the anisotropy as seen in scanning tunneling microscopy experiments. The restructuring rate depends nonlinearly on the CO coverage, but the absence of local clustering of CO excludes an explanation in terms of elementary reaction kinetics as proposed previously.