Several mechanisms and intermediate steps have been proposed to explain the transformation of graphite to diamond. However, the mechanism continues to be debated, in part because graphite that is incompletely transformed to diamond has not been reported; although such material could be used to better understand the diamond-forming process. Here we report the discovery of nano-sized grains of interstratified graphite and diamond from Gujba, an extraterrestrially shocked meteorite. We use high-resolution transmission electron microscopy (HRTEM) data from these grains to show that diamond formed via a reconstructive, topotactic rather than martensitic mechanism. Electron diffraction and HRTEM images show the following three-dimensional crystallographic relationships between the interstratified graphite and diamond: (001)g||(111)d, (100)g||(21̄1̄)d, and (12̄0)g||(01̄1)d. These relationships yield the transition matrix linking the graphite and diamond unit cells, which become coincident for graphite compressed to 7 GPa. The specific product, whether single-crystal or twinned diamond, is dictated by the initial graphite polytype and transformation route. The derivation of a three-dimensional transition matrix is consistent with a topotactic relationship between graphite and the newly formed diamond.