Predicting when phase changes occur in nanoparticles is fundamental for designing the next generation of devices suitable for catalysis, biomedicine, optics, chemical sensing and electronic circuits. The estimate of the temperature at which metallic nanoparticles become liquid is, however, a challenge and a standard definition is still missing. We discover a universal feature in the distribution of the atomic-pair distances that distinguishes the melting transition of monometallic nanoparticles. We analyse the solid-liquid change of several late-transition metals nanoparticles, i.e. Ni, Cu, Pd, Ag, Au and Pt, through classical molecular dynamics. We consider various initial shapes from 146 to 976 atoms, corresponding to the 1.5-4.1 nm size range, placing the nanoparticles in either a vacuum or embedded in a homogeneous environment, simulated by an implicit force-field. Regardless of the material, its initial shape, size and environment, the second peak in the pair-distance distribution function, expected at the bulk lattice distance, disappears when the nanoparticle melts. As the pair-distance distribution is a measurable quantity, the proposed criterion holds for both numerical and experimental investigations. For a more straightforward calculus of the melting temperature, we demonstrate that the cross-entropy between a reference solid pair-distance distribution function and the one of nanoparticles at increasing temperatures present a quasi-first order transition at the phase-change temperature.