Elucidating the roles played by carbon solubility in catalyst nanoparticles is required to better understand the growth mechanisms of single-walled carbon nanotubes (SWNTs). Here, we highlight that controlling the level of dissolved carbon is of key importance to enable nucleation and growth. We first performed tight binding based atomistic computer simulations to study carbon incorporation in metal nanoparticles with low solubilities. For such metals, carbon incorporation strongly depends on their structures (face centered cubic or icosahedral), leading to different amounts of carbon close to the nanoparticle surface. Following this idea, we then show experimentally that Au nanoparticles effectively catalyze SWNT growth when in a face centered cubic structure, and fail to do so when icosahedral. Both approaches emphasize that the presence of subsurface carbon in the nanoparticles is necessary to enable the cap lift-off, making the nucleation of SWNTs possible.