The size dependency of the critical temperature (TC) for the order–disorder phase transitions of both the bimetallic and the chalcogenide nanoclusters is shown to follow the rule of bond order–length–strength correlation. The loss of the cohesive energy of the undercoordinated atoms in the surface skin dictates the structural stability. Theoretical reproduction of the size TC trends of FePt, CoPt, FePb, Cu2S, and ZnS nanostructures not only confirms our expectations without involving the concepts of surface energy or entropy used for continuum bulk materials but also provides guideline for engineering nanostructured alloys or compounds.