Using scanning tunneling microscopy, we show that Pt clusters can be encapsulated beneath the surface of graphite, whereas Ag and Au cannot. This is in complete agreement with independent predictions from density functional theory, which show that surface intercalation of single metal atoms is favorable for Pt, but unfavorable for Ag and Au. This supports the validity of using single-metal-atom energetics for predicting encapsulation of metal nanoparticles at the graphite surface. We also demonstrate that the optimal temperature for encapsulation scales with the cohesive energy of the metal.