As one of the most robust global optimization methods, simulated annealing has received considerable attention with many variations that attempt to improve the cooling schedule. This paper introduces a variant of molecular dynamics-based simulated annealing that is useful for optimizing atomistic structures, and makes use of the heat capacity of the system, determined on the fly during optimization, to adaptively control the cooling rate. This adaptive cooling approach is demonstrated to be more computationally efficient than classical simulated annealing when applied to Lennard-Jones clusters. The increase in efficiency is approximately a factor of two for clusters with 25–40 atoms, and improves as the size of the system increases.