One of the well-known observations in the Fischer-Tropsch (FT) reaction is that the CH4 selectivity for cobalt catalysts is always higher than the value expected on the basis of the Anderson-Schulz-Flory (ASF) distribution. Depositing graphitic carbon on a cobalt catalyst strongly suppresses this non-ASF CH4, while the formation of higher hydrocarbons is much less affected. Carbon was laid down on the cobalt catalyst via the Boudouard reaction. We provide evidence that the amorphous carbon does not influence the FT reaction, as it can be easily hydrogenated under reaction conditions. Graphitic carbon is rapidly formed and cannot be removed. This unreactive form of carbon is located on terrace sites and mainly decreases the CO conversion by limiting CH4 formation. Despite nearly unchanged higher hydrocarbon yield, the presence of graphitic carbon enhances the chain-growth probability and strongly suppresses olefin hydrogenation. We demonstrate that graphitic carbon will slowly deposit on the cobalt catalysts during CO hydrogenation, thereby influencing CO conversion and the FT product distribution in a way similar to that for predeposited graphitic carbon. We also demonstrate that the buildup of graphitic carbon by 13CO increases the rate of C-C coupling during the 12C3H6 hydrogenation reaction, whose products follow an ASF-type product distribution of the FT reaction. We explain these results by a two-site model on the basis of insights into structure sensitivity of the underlying reaction steps in the FT mechanism: carbon formed on step-edge sites is involved in chain growth or can migrate to terrace sites, where it is rapidly hydrogenated to CH4. The primary olefinic FT products are predominantly hydrogenated on terrace sites. Covering the terraces by graphitic carbon increases the residence time of CH x intermediates, in line with decreased CH4 selectivity and increased chain-growth rate.