A novel growth mechanism of graphene on Ni(111) has been discovered that occurs at temperatures below 460 °C. At these conditions, a surface-confined nickel-carbide phase coexists with single layer graphene. The graphene grows by in-plane transformation of the carbide along a one-dimensional phase-boundary, which is distinctively different from known growth processes on other transition metals and on Ni above 460 °C, where carbon atoms attach to "free" edges of graphene islands.