Graphene nucleation on Ni(111) has been modeled using QM/MD simulations. We demonstrate that graphene precursor nucleation can occur underneath the catalyst surface. In addition, a Ni(111) step-edge is not a static structure, as is often assumed; it is instead highly malleable, being deformed and subsequently healed during graphene nucleation.