Graphene has a close lattice match to the Ni(111) surface, resulting in a preference for 1 × 1 configurations. We have investigated graphene grown by chemical vapor deposition (CVD) on the nickel carbide (Ni(2)C) reconstruction of Ni(111) with scanning tunneling microscopy (STM). The presence of excess carbon, in the form of Ni(2)C, prevents graphene from adopting the preferred 1 × 1 configuration and leads to grain rotation. STM measurements show that residual Ni(2)C domains are present under rotated graphene. Nickel vacancy islands are observed at the periphery of rotated grains and indicate Ni(2)C dissolution after graphene growth. Density functional theory (DFT) calculations predict a very weak (van der Waals type) interaction of graphene with the underlying Ni(2)C, which should facilitate a phase separation of the carbide into metal-supported graphene. These results demonstrate that surface phases such as Ni(2)C can play a major role in the quality of epitaxial graphene.