Cluster migration is known to be an important process during film growth at elevated temperatures, but relatively little quantitative data is available. We have used molecular dynamics simulations to follow the dynamics of small two-dimensional Pt clusters on Pt(lll) at 1000 K. While close-packed Pt-7 heptamers are extremely stable structures, the addition of a single-cluster vacancy or an on-top adatom immediately results in intracluster bond breaking, reconfigurations, rotations, the introduction of stacking faults, and greatly enhanced cluster-diffusion rates. Mapping center-of-mass motion for total simulation times > 145 ns revealed increases in cluster velocities by more than an order of magnitude with cluster migration occurring primarily by concerted motion and a novel diffusion mechanism involving double shearing of dimers/trimers. Contrary to some previous reports, edge-atom diffusion plays only a minor role.