Cerium oxide is an important catalytic material known for its ability to store and release oxygen, and as such, it has been used in a range of applications, both as an active catalyst and as a catalyst support. Using scanning tunneling microscopy and Auger electron spectroscopy, we investigated oxygen interactions with CeO x nanoclusters on a complete graphene monolayer-covered Ru(0001) surface at elevated temperatures (600–725 K). Under oxidizing conditions (P O2 = 1 × 10–7 Torr), oxygen intercalation under the graphene layer is observed. Time dependent studies demonstrate that the intercalation proceeds via spillover of oxygen from CeO x nanoclusters through the graphene (Gr) layer onto the Ru(0001) substrate and extends until the Gr layer is completely intercalated. Atomically resolved images further show that oxygen forms a p(2 × 1) structure underneath the Gr monolayer. Temperature dependent studies yield an apparent kinetic barrier for the intercalation of 1.21 eV. This value correlates well with the theoretically determined value for the reduction of small CeO2 clusters reported previously. At higher temperatures, the intercalation is followed by a slower etching of the intercalated graphene (apparent barrier of 1.60 eV). Vacuum annealing of the intercalated Gr leads to the formation of carbon monoxide, causing etching of the graphene film, demonstrating that the spillover of oxygen is not reversible. In agreement with previous studies, no intercalation is observed on a complete graphene monolayer without CeO x clusters, even in the presence of a large number of point defects. These studies demonstrate that the easily reducible CeO x clusters act as intercalation gateways capable of efficiently delivering oxygen underneath the graphene layer.