O2 oxidation and sublimation kinetics for >30 individual nanoparticles (NPs) of five different feedstocks (graphite, graphene oxide, carbon black, diamond, and nano-onion) were measured using single-NP mass spectrometry at temperatures (TNP) in the 1100-2900 K range. It was found that oxidation, studied in the 1200-1600 K range, is highly sensitive to the NP surface structure, with etching efficiencies (EEO2) varying by up to 4 orders of magnitude, whereas sublimation rates, significant only for TNP ≥ ∼1700 K, varied by only a factor of ∼3. Its sensitivity to the NP surface structure makes O2 etching a good real-time structure probe, which was used to follow the evolution of the NP surface structures over time as they were either etched or annealed at high TNP. All types of carbon NPs were found to have initial EEO2 values in the range near 10-3 Da/O2 collision, and all eventually evolved to become essentially inert to O2 (EEO2 < 10-6 Da/O2 collision); however, the dependence of EEO2 on time and mass loss was very different for NPs from different feedstocks. For example, diamond NPs evolved rapidly and monotonically toward inertness, and evolution occurred in both oxidizing and inert atmospheres. In contrast, graphite NPs evolved only under oxidizing conditions and were etched with complex time dependence, with multiple waves of fast but non-monotonic etching separated by periods of near-inertness. Possible mechanisms to account for the complex etching behavior are proposed.