Carbon is a critical material for existing and emerging energy applications and there is considerable global effort in generating sustainable carbons. A particularly promising area is iron-catalyzed graphitization, which is the conversion of organic matter to graphitic carbon nanostructures by an iron catalyst. In this paper, it is reported that iron-catalyzed graphitization occurs via a new type of mechanism that is called homogeneous solid-state catalysis. Dark field in situ transmission electron microscopy is used to demonstrate that crystalline iron nanoparticles “burrow” through amorphous carbon to generate multiwalled graphitic nanotubes. The process is remarkably fast, particularly given the solid phase of the catalyst, and in situ synchrotron X-ray diffraction is used to demonstrate that graphitization is complete within a few minutes.