Co-Pt and Co-Au core-shell nanoparticles were heated by molecular dynamics simulations to investigate their thermal stability. Two core structures, that is, hcp Co and fcc Co, have been addressed. The results demonstrate that the hcp-fcc phase transition happens in the hcp-Co-core/fcc-Pt-shell nanoparticle, while it is absent in the hcp-Co-core/fcc-Au-shell one. The stacking faults appear in both Pt and Au shells despite different structures of the Co core. The Co core and Pt shell concurrently melt and present an identical melting point in both Co-Pt core-shell nanoparticles. However, typical two-stage melting occurs in both Co-Au core-shell nanoparticles. Furthermore, the Au shell in the hcp-Co-core/fcc-Au-shell nanoparticle exhibits a lower melting point than that in the fcc-Co-core/fcc-Au-shell one, while the melting points are closely equal for both hcp and fcc Co cores. All of these observations suggest that their thermal stability strongly depends on the structure of the core and the element of the shell.