The thermal characteristics of bimetallic Pt-Pd nanoparticles, both free and graphite-supported, were investigated through molecular dynamics simulations using quantum Sutton-Chen many-body potentials for the metal-metal interactions. The graphite substrate was represented as layers of fixed carbons sites and modeled with the Lennard-Jones potential model. The melting temperatures for bimetallic nanoparticles were estimated based on variations in thermodynamic properties such as potential energy and heat capacity. Melting temperatures of the nanoparticles were found to be considerably lower than those of bulk Pt and Pd. The Pt-Pd clusters exhibited a two-stage melting, where surface melting of the external atoms is followed by homogeneous melting of the internal atoms. The melting transition temperature was found to increase when the particle is on the graphite support, with an increase at least 180 K higher than that of the same-sized free nanoparticle. The results of the density distributions perpendicular to the surface indicate that the Pd atoms have a tendency to remain at the surface, and the Pd atoms wet the graphite surface more than the Pt atoms, while root mean squares suggest that surface melting starts from the cluster surface, and surface melting was seen in both free and graphite-supported nanoparticles. Structural changes accompanying the thermal evolution were studied by the bond-orientational order parameter method.