Mineralogical structures of carbon phases within the ureilite North West Africa 4742, a recent find, are investigated at various scales by high-resolution transmission electron microscopy (HRTEM), Raman microspectrometry and X-ray diffraction. Ureilites are the most carbon-rich of all meteorites, containing up to 6 wt.% carbon. Diamond, graphite and so-called "amorphous carbon" are typically described, but their crystallographic relationships and respective thermal histories remain poorly constrained. We especially focus on the origin of "amorphous carbon" and graphite, as well as their relationship with diamond. Two aliquots of carbon-bearing material were extracted: the insoluble organic matter (IOM) and the diamond fraction. We also compare the observed structures with those of laboratory-shocked graphite. Polycrystalline diamond aggregates with mean coherent domains of about 40 nm are reported for the first time in a ureilite and TEM demonstrates that all carbon phases are crystallographically related at the nanometre scale. Shock features show that diamond is produced from graphite through a martensitic transition. This observation demonstrates that graphite was present when the shock occurred and is consequently a precursor of diamond. The structure of what is commonly described as the "amorphous carbon" has been identified. It is not completely amorphous but only disordered and consists of nanometre-sized polyaromatic units surrounding the diamond. Comparison with laboratory-shocked graphite, partially transformed into diamond, indicates that the disordered carbon could be the product of diamond post-shock annealing. As diamond is the carrier of noble gases, whereas graphite is noble gas free, graphite cannot be the sole diamond precursor. This implies a multiple-stage history. A first generation of diamond could have been synthesized from a noble gas rich precursor or environment by either a shock or a condensation process. Thermally-induced graphitization of chondritic-like organic matter could have produced the graphite, which was then transformed by shock processes into polycrystalline nanodiamond aggregates. The formation of the disordered carbon occurred by diamond post-shock back-transformation during post-shock heating. The noble gases in the first generation diamond could then be incorporated directly into the disordered carbon during the transformation.