In the present study, molecular dynamics simulations have been utilized to provide fundamental understanding of melting behavior of pure Pd and Pt nanoparticles with the size of 10 nm in diameter, both free and graphene-supported during continuous heating. The embedded atom method is employed to model the metal-metal interactions, whereas a Lennard-Jones potential is applied to describe the metal-carbon interactions. In addition, interactions between carbon atoms are defined by the adaptive intermolecular reactive bond order potential. Heating curves calculated between 298 K-2000 K are used to determine solid-liquid transitions. Based on simulation results, three approaches are used to investigate the thermal behavior of Pd and Pt nanoparticles. These include potential energy variation, the percentage of FCC atoms as a function of temperature and the mean square displacement method. Melting temperature of nanoparticles is found to decrease when the particles are supported by the graphene substrate. The decrease in melting temperature of particles is ascribed to the interaction of carbon atoms with nanoparticles. Structural changes during melting of nanoparticles are also detected through the common neighbor analysis and the mean square displacement method. The analyses of crystal structure shows that the supported nanoparticles melt from surface. In addition, a sharp increase in the mean square displacement of supported nanoparticles is observed after melting which is suggested to be responsible for the reduction of melting point of nanoparticles.