The ultrafast laser excitation of matters leads to nonequilibrium states with complex solid-liquid phase-transition dynamics. We used electron diffraction at mega-electron volt energies to visualize the ultrafast melting of gold on the atomic scale length. For energy densities approaching the irreversible melting regime, we first observed heterogeneous melting on time scales of 100 to 1000 picoseconds, transitioning to homogeneous melting that occurs catastrophically within 10 to 20 picoseconds at higher energy densities. We showed evidence for the heterogeneous coexistence of solid and liquid. We determined the ion and electron temperature evolution and found superheated conditions. Our results constrain the electron-ion coupling rate, determine the Debye temperature, and reveal the melting sensitivity to nucleation seeds.