Density functional theory is used to evaluate the adsorption of carbon on stepped (211) cobalt surfaces. It is found that the 4-fold step hollow sites on (100) planes are the most stable adsorption sites for carbon, followed by the 3-fold hcp sites located in (111) terraces where adsorption per carbon atom is 0.7−0.9 eV less stable than that on the step sites. When the carbon concentration over the surface increases, adsorption of carbon chains is also favorable, and at even higher carbon pressures, interaction of adsorbed chains may lead to the formation of graphene sheets parallel to the (100) plane or to the formation of horizontally aligned semi-nanotubes. Formation of these carbon structures is accompanied by oxidation of the cobalt atoms, especially those forming the 4-fold step hollow site, whereas cobalt terrace sites become negatively charged. We discuss the significance of our results in relation to the catalyzed growth of single-walled carbon nanotubes on cobalt nanoparticles.