Quantum chemical molecular dynamics simulations of graphene nucleation on the Ni(111) surface show that graphene creates its own step-edge as it forms. This "step-edge self-assembly" is driven by the formation of thermodynamically favorable Ni-C σ-bonds at the graphene edge. This dynamic aspect of the Ni(111) catalyst is in contrast to the commonly accepted view that graphene nucleates on a pre-existing, static catalyst step-edge. Simulations also show that, simply by manipulating the subsurface carbon density, preferential formation of single-layer graphene instead of multi-layer graphene can be achieved on nickel catalysts.