Graphite and diamond have comparable free energies, yet forming diamond from graphite in the absence of a catalyst requires pressures that are significantly higher than those at equilibrium coexistence(1-7). At lower temperatures, the formation of the metastable hexagonal polymorph of diamond is favoured instead of the more stable cubic diamond(2,5-7). These phenomena cannot be explained by the concerted mechanism suggested in previous theoretical studies(8-12). Using an ab initio quality neural-network potential(13), we carried out a large-scale study of the graphite-to-diamond transition assuming that it occurs through nucleation. The nucleation mechanism accounts for the observed phenomenology and reveals its microscopic origins. We demonstrate that the large lattice distortions that accompany the formation of diamond nuclei inhibit the phase transition at low pressure, and direct it towards the hexagonal diamond phase at higher pressure. The proposed nucleation mechanism should improve our understanding of structural transformations in a wide range of carbon-based materials.