Density functional theory is used to study structural energetics of Pb vacancy cluster formation on C60/Pb/Si(111) to explain the unusually fast and error-free transformations between the “Devil's Staircase” (DS) phases on the Pb/Si(111) wetting layer at low temperature (∼110K). The formation energies of vacancy clusters are calculated in C60/Pb/Si(111) as Pb atoms are progressively ejected from the initial dense Pb wetting layer. Vacancy clusters larger than five Pb atoms are found to be stable with seven being the most stable, while vacancy clusters smaller than five are highly unstable, which agrees well with the observed ejection rate of ∼5 Pb atoms per C60. The high energy cost (∼0.8 eV) for the small vacancy clusters to form indicates convincingly that the unusually fast transformation observed experimentally between the DS phases, upon C60 adsorption at low temperature, cannot be the result of single-atom random walk diffusion but of correlated multi-atom processes.