Understanding of carbon nanomaterials oxidation is useful in many different applications, e.g., for soot emission abatement, or in defect engineering aiming to improve material properties. In this work, the oxidative behavior of three substantially different qualities of carbon black, multiwall carbon-nanotubes, and few-layer graphene, was studied using a combination of macroscale quantification (using thermogravimetric analysis) and nanoscale imaging of their structural evolution (using environmental transmission electron microscopy, ETEM). The materials were investigated both with and without the addition of a nanoparticulate iron oxide catalyst. Catalyst addition clearly lowered the conversion temperature during oxidation. The ETEM revealed that the catalyst nanoparticles induced primary surface damages in the carbon nanostructure at relatively low temperatures. From there, oxidation could proceed more rapidly at recently exposed edge sites due to their higher propensity for oxidation. Thus, the enhanced oxidation was not solely linked to the interface between catalyst and carbon.