We performed an experiment to study the thermal stability of metal on graphene. We show that Fe, Gd, Dy, and Eu on graphene exhibit island growth morphology. The 3D islands of Fe, Gd, and Dy show a small decrease in island density and an increase in the height/width aspect ratio upon thermal annealing. By contrast, coarsening of Eu islands to a close flat film is observed after annealing to 365 K. By investigating the fundamental interactions (i.e., adsorption energies and diffusion barriers) between the metal adatoms and graphene using ab initio calculations, we predict that most of the 3d and group 10 transition metals, noble metals, as well as rare earth metals on graphene should exhibit a 3D growth mode as observed in experiment. Most of the metal nanostructures on graphene should also be stable against aggregation. The 3D morphology and strong thermal stability of Fe, Co, Ni, Pt, and Gd islands on graphene can serve as good candidates for surface-supported catalysis applications.