We have built a lattice gas model for cobalt-carbon interaction to investigate the thermodynamics and kinetics of carbon deposition on Co(0001) surfaces. The formation of carbon structures on cobalt is considered to be one of the causes of deactivation of a cobalt Fischer-Tropsch (FT) catalyst. The formation of graphene - the most thermodynamically stable phase under FT conditions - is kinetically inhibited during the first 30 hours of exposure of the surface to carbon, while the build-up of surface carbide is the fastest reaction. Our simulations clearly show that the kinetics of carbon deposition is the result of two competing effects: a fast subsurface diffusion and a slower surface diffusion to form a carbon-carbon bond.