The nucleation pathway for single-wall carbon nanotubes on a metal surface is demonstrated by a series of total energy calculations using density functional theory. Incorporation of pentagons at an early stage of nucleation is energetically favorable as they reduce the number of dangling bonds and facilitate curvature of the structure and bonding to the metal. In the presence of the metal surface, nucleation of a closed cap or a capped single-wall carbon nanotube is overwhelmingly favored compared to any structure with dangling bonds or to a fullerene.