The nucleation of graphene on a transition metal surface, either on a terrace or near a step edge, is systematically explored using density functional theory calculations and applying the two-dimensional (2D) crystal nucleation theory. Careful optimization of the supported carbon clusters, C(N) (with size N ranging from 1 to 24), on the Ni(111) surface indicates a ground state structure transformation from a one-dimensional C chain to a 2D sp(2) C network at N ≈ 10-12. Furthermore, the crucial parameters controlling graphene growth on the metal surface, nucleation barrier, nucleus size, and nucleation rate on a terrace or near a step edge are calculated. In agreement with numerous experimental observations, our analysis shows that graphene nucleation near a metal step edge is superior to that on a terrace. On the basis of our analysis, we propose the use of graphene seeds to synthesize high-quality graphene in large area.