Molecular dynamics (MD) simulations have been used to investigate the melting processes of 55-atom and 561-atom Pt–Au nanoalloys with random (RD) and core-shell (CS) orderings. The simulation results show that the Pt–Au CS nanoalloys have higher thermal and structural (including geometrical shape and chemical ordering) stability than the RD ones with the same size and composition. For all the CS nanoalloys studied, their geometric shape and chemical ordering are preserved well before the complete melting transition occurs and their premelting corresponds to the surface melting. In the RD ordering cases, nevertheless, obvious shape distortion and chemical order transformation are observed during the premelting stage. The nature of premelting of the 55-atom RD nanoalloy is not surface melting but dynamic coexistence melting. Additionally, the melting behavior of the RD nanoalloys is found to depend on the particle size. Several separated ordering transformation stages associated with the mutual conversion of different geometrical structures can be observed in the smaller 55-atom particle instead of the 561-atom case. These results suggest that different atomic orderings of nanoalloys can lead to distinctive melting features.