To understand the nucleation of carbon atoms to form carbon clusters on transition metal substrates during chemical vapor deposition (CVD) synthesis, the structure, energetics, and mobility of carbon intermediates up to 6 atoms on the Ni(111) surface were investigated using Density Functional Theory (DFT). Carbon clusters were found to be more thermodynamically stable than adsorbed atomic carbon, with linear carbon structures being more stable than branched and ring structures. Carbon chains were also found to have higher mobility than branched configurations. The interaction energy between carbon clusters and the Ni surface shows that branched carbon clusters have stronger interaction with the Ni substrate when compared with the carbon chains, supporting that carbon chains generally have higher mobility than branched clusters. The transition states and energy barriers for the formation of different carbon clusters were also studied. The results show that the formation of the branched configurations is kinetically favored as it presents lower energy barriers than those obtained for carbon chains.