Atomic carbon on Co(0001), deposited by ethylene decomposition, forms islands with a (v3 × v3)R30° structure at low C coverage (0.2 ML), whereas a high C coverage (0.5 ML, saturation) induces a reconstruction of the cobalt surface. Atomic carbon weakens the adsorption of CO and H2, but even a saturated atomic carbon layer does not block the surface for adsorption. Carbon–carbon coupling, i.e., polymeric carbon formation, was not observed for temperatures =630 K on the close-packed cobalt surface. Polymeric carbon, in the form of small graphene islands, forms on the close-packed terraces after heating of an acetylene-saturated surface. Graphene also forms upon heating of an atomic carbon covered surface on which ethylene was dosed at low temperature. In this case, step edges act as a nucleation point of the graphene islands, while their growth proceeds via the addition of C2Hx species. In both cases, hydrogenated forms of carbon rather than atomic carbon are key precursors for graphene growth. Graphene covers the cobalt surface, thereby inhibiting adsorption of CO and hydrogen completely. The described graphene formation mechanism is seen as a relevant, low temperature route to detrimental carbon that would deactivate a cobalt FT catalyst. Atomic carbon is more reactive than graphene, as it is oxidized at lower temperatures than graphene. The graphene islands formed at relatively low temperatures are of poor structural quality and contain (islands of) encapsulated cobalt atoms.