We systematically study the effects of residual oxygen in the bulk of Cu foil catalysts on the chemical vapor deposition (CVD) of graphene. While oxidation is widely used to remove impurities in metal catalysts and to control the nucleation density of graphene, we show that minute concentrations of residual bulk oxygen can significantly deteriorate the quality of as-grown graphene highlighted by an increased Raman D/G ratio, increased propensity to postgrowth etching, and increased fraction of multilayer graphene nucleation. Starting from commercial Cu foils, we show that a simple hydrogen annealing step after the initial oxidation allows us to lower the residual oxygen level as measured by time-of-flight secondary ion mass spectrometry to produce graphene of significantly higher quality. This can be effectively combined with a short hydrocarbon exposure time of 10 min to achieve near full monolayer graphene coverage, suitable for emerging industrial applications. We show that residual oxygen can have an equally significant impact on Fe-catalyzed h-BN CVD and discuss the underlying mechanisms with parallels to well-known processes in metallurgy, catalysis, and vacuum science.