Fabrication of high-performance heterostructure devices requires fundamental understanding of the diffusion dynamics of metal species on 2D materials. Here, we investigate the room-temperature diffusion of Ag, Au, Cu, Pd, Pt, and Ru adatoms on graphene using ab initio and classical molecular dynamics simulations. We find that Ag, Au, Cu, and Pd follow Lévy walks, in which adatoms move continuously within ∼1–4 nm2 domains during ∼0.04 ns timeframes, and they occasionally perform ∼2–4 nm flights across multiple surface adsorption sites. This anomalous diffusion pattern is associated with a flat (<50 meV) potential energy landscape (PEL), which renders surface vibrations important for adatom migration. The latter is not the case for Pt and Ru, which encounter a significantly rougher PEL (>100 meV) and, hence, migrate via conventional random walks. Thus, adatom anomalous diffusion is a potentially important aspect for modeling growth of metal films and nanostructures on 2D materials.