The atomic-scale processes that control the formation of carbon deposits on Ni catalysts in reforming applications are poorly understood. Ab initio Density Functional Theory calculations have been used to examine several key elementary steps in the complex network of chemical reactions that precedes carbon formation on practical catalysts. Attention has been focused on the disproportionation of CO. A comparative study of this reaction on flat and stepped crystal planes of Ni has provided the first direct evidence that surface carbon formation is driven by elementary reactions occurring at defect sites on Ni catalysts. The adsorption and diffusion of atomic H on several flat and stepped Ni surfaces has also been characterized experimentally.