Oxygen contamination is a problem which inevitably occurs during severe plastic deformation of metallic powders by exposure to air. Although this contamination can change the morphology and properties of the consolidated materials, there is a lack of detailed information about the behavior of oxygen in nanocrystalline alloys. In this study, aberration-corrected high-resolution transmission electron microscopy and associated techniques are used to investigate the behavior of oxygen during in situ heating of highly strained Cu-Fe alloys. Contrary to expectations, oxide formation occurs prior to the decomposition of the metastable Cu-Fe solid solution. This oxide formation commences at relatively low temperatures, generating nanosized clusters of firstly CuO and later Fe2O3. The orientation relationship between these clusters and the matrix differs from that observed in conventional steels. These findings provide a direct observation of oxide formation in single-phase Cu-Fe composites and offer a pathway for the design of nanocrystalline materials strengthened by oxide dispersions.