The melting transition of Ce adatom superlattices stabilized by long-range substrate-mediated electronic interactions on Cu(111) and Ag(111) noble metal surfaces has been investigated by low-temperature scanning tunneling microscopy, density functional theory calculations, and kinetic Monte Carlo simulations. Intriguingly, owing to the interaction between Ce adatoms and substrate, these superlattices undergo two-dimensional melting to a liquid without transition through the hexatic phase. The crucial parameters for this direct solid to liquid transition are identified.