The long-term (>18 months) protection of Ni surfaces against oxidation under atmospheric conditions is demonstrated by coverage with single-layer graphene, formed by chemical vapor deposition. In situ, depth-resolved X-ray photoelectron spectroscopy of various graphene-coated transition metals reveals that a strong graphene-metal interaction is of key importance in achieving this long-term protection. This strong interaction prevents the rapid intercalation of oxidizing species at the graphene-metal interface and thus suppresses oxidation of the substrate surface. Furthermore, the ability of the substrate to locally form a passivating oxide close to defects or damaged regions in the graphene overlayer is critical in plugging these defects and preventing oxidation from proceeding through the bulk of the substrate. We thus provide a clear rationale for understanding the extent to which two-dimensional materials can protect different substrates and highlight the key implications for applications of these materials as barrier layers to prevent oxidation.