Experiments probing O2 oxidation, sublimation, and annealing kinetics for carbon NPs demonstrated that O2 etching efficiency is a sensitive probe of NP surface structure, allowing the structural evolution of NPs to be studied in detail. Different types of carbon NPs all have similar initial EEO2 values, and all eventually evolve to become nearly inert to O2 attack, but the trajectory of the evolution varies substantially between different materials, and from NP-to-NP within each material type.