Molecular dynamics simulations with many-body interatomic potentials are used to study melting of Ni and Fe nanoparticles with diameters that range between 2 and 12 nm. Two different embedded-atom method interatomic potentials are used for each element. The capability of each interatomic potential to model (i) size-dependent melting in nanoparticles and (ii) the bulk melting temperature of Ni or Fe is explored. In agreement with existing theory, molecular dynamics simulations show that the melting temperature of non-supported nanoparticles decreases with decreasing nanoparticle size, displaying a linear relationship with the inverse of nanoparticle diameter. However, molecular dynamics simulations using the interatomic potentials considered in this work provide a lower estimate than existing theory for the sensitivity of the melting temperature to nanoparticle size (slope of linear relationship). Molecular dynamics simulations demonstrate that melting is surface initiated and that a finite temperature range exists in which partial melting of the nanoparticle occurs. This observation is very important in the development of advanced vapor-liquid-solid models for catalyst-assisted single-walled carbon nanotube synthesis.