X-ray structural science is undergoing a revolution driven by the emergence of X-ray Free-electron Laser (XFEL) facilities. The structures of crystalline solids can now be studied on the picosecond time scale relevant to phonons, atomic vibrations which travel at acoustic velocities. In the work presented here, X-ray diffuse scattering is employed to characterize the time dependence of the liquid phase emerging from femtosecond laser-induced melting of polycrystalline gold thin films using an XFEL. In a previous analysis of Bragg peak profiles, we showed the supersonic disappearance of the solid phase and presented a model of pumped hot electrons carrying energy from the gold surface to scatter at internal grain boundaries. This generates melt fronts propagating relatively slowly into the crystal grains. By conversion of diffuse scattering to a partial X-ray pair distribution function, we demonstrate that it has the characteristic shape obtained by Fourier transformation of the measured F(Q). The diffuse signal fraction increases with a characteristic rise-time of 13 ps, roughly independent of the incident pump fluence and consequent final liquid fraction. This suggests the role of further melt-front nucleation processes beyond grain boundaries.