The temperature-induced structural changes of Fe-, Co-, and Ni-Au core-shell nanoparticles with diameters around 5 nm are studied via atomically resolved transmission electron microscopy. We observe structural transitions from local toward global energy minima induced by elevated temperatures. The experimental observations are accompanied by a computational modeling of all core-shell particles with either centralized or decentralized core positions. The embedded atom model is employed and further supported by density functional theory calculations. We provide a detailed comparison of vacancy formation energies obtained for all materials involved in order to explain the variations in the restructuring processes which we observe in temperature-programmed TEM studies of the particles.