The structural evolution of carbon nanofibers submitted to high-temperature (1800, 2300, and 2800 °C) heat treatments has been investigated at the nanometric and atomic scales by means of scanning tunneling microscopy (STM). To complement the local STM observations, X-ray diffraction and Raman spectroscopy characterization of the samples were also carried out. On the nanometer scale, the as-grown nanofibers displayed an isotropic platelet morphology that developed into striped arrangements of increasing width at 1800 and 2300 °C, and into large, atomically flat terraces at 2800 °C. On the atomic scale, the starting nanofibers were characterized by tiny (≲2 nm) crystallites. The crystallites were observed to coalesce at 1800 °C into appreciably larger (∼3–4 nm) although still defective units. Atomic structures evidencing truly graphitic ordering (i.e. the typical STM triangular pattern with a periodicity of 0.25 nm) started to develop at 2300 °C. At this temperature, a segregation of graphitic domains and highly defective areas was noticed and attributed mainly to the mobility and subsequent aggregation of point defects (atomic vacancies). Long-range atomic-scale order was generally established in the nanofibers heat treated at 2800 °C, where only some incompletely graphitized, fragmentary graphenes were left on the surface.