We have used ab initio methods to study the possible transition between icosahedral (ico) and cuboctahedral (fcc) structures in lead nanoclusters of sizes up to 309 atoms. Spontaneous fcc-to-ico transition in Pb-13 was observed in the ab initio molecular dynamics (MD) simulations at various temperatures. The transition path can be described predominantly by an angular variable s, which can, generally be applied to the similar transitions in clusters of larger sizes and was observed to follow the Mackay model. We have calculated the two-dimensional energy surface that describes the transition in Pb-13 and found a barrierless fcc-to-ico transition path, which is consistent with the observed spontaneous transition in the ab initio MD simulations. The atomic displacements in the transition were identified as one of the vibrational eigenmodes of these two Pb-13 clusters. For clusters of larger sizes (Pb-n, where n = 55, 147, and 309), the possible transitions following similar paths were determined not to be barrierless and the sizes of the barriers were determined by the ab initio elastic band method.