We used 600-femtosecond electron pulses to study the structural evolution of aluminum as it underwent an ultrafast laser-induced solid-liquid phase transition. Real-time observations showed the loss of long-range order that was present in the crystalline phase and the emergence of the liquid structure where only short-range atomic correlations were present; this transition occurred in 3.5 picoseconds for thin-film aluminum with an excitation fluence of 70 millijoules per square centimeter. The sensitivity and time resolution were sufficient to capture the time-dependent pair correlation function as the system evolved from the solid to the liquid state. These observations provide an atomic-level description of the melting process, in which the dynamics are best understood as a thermal phase transition under strongly driven conditions.