Using scanning tunneling microscopy, x-ray photoelectron spectroscopy, and x-ray absorption spectroscopy, we show that Ru forms metallic nanoislands on graphite, covered by a graphene monolayer. These islands are air-stable, contain 2–4 layers of Ru, and have diameters on the order of 10 nm. To produce these nanoislands two conditions must be met during synthesis. The graphite surface must be ion-bombarded, and subsequently held at an elevated temperature (1000–1180 K) during Ru deposition. A coincidence lattice forms between the graphene overlayer and the Ru island top. Its characteristics—coincidence lattice constant, corrugation amplitude, and variation of carbon lattice appearance within the unit cell—closely resemble the well-established characteristics of single-layer graphene on the (0001) surface of bulk Ru. Quantitative analysis of the graphene lattice in relation to the coincidence lattice on the island tops show that the two-dimensional lattice constant of the underlying metal equals that of bulk Ru(0001), within experimental error. The embedded Ru islands are energetically favored over on-top (adsorbed) islands, based on density-functional-theory calculations for Ru films with 1–3 Ru layers. We propose a formation mechanism in which Ru atoms intercalate via defects that act as entry portals to the carbon galleries, followed by nucleation and growth in the galleries. In this model, high deposition temperature is necessary to prevent blockage of entry portals.