The thermal stability boundaries of initial f.c.c. phase within the Al and Pb nanoclusters with a diameter of up to 3.0 nm are investigated by the molecular dynamics method using modified tight-binding potential (TB-SMA). The simulation indicates that the structural transition in small Al and Pb clusters from the initial f.c.c. phase to other modifications, including ones with pentagonal symmetry, occurs under the influence of temperature factor. The transition temperature is shifted towards the cluster melting temperature with an increase in the cluster size. As determined, the geometrical ‘magic’ numbers play a major role in a structure formation for aluminium clusters, unlike lead clusters.