Due to its extremely short timescale, the non-equilibrium melting of metals is exceptionally difficult to probe experimentally. The knowledge of melting mechanisms is thus based mainly on the results of theoretical predictions. This work reports on the investigation of ultrafast melting of thin polycrystalline Pd films studied by optical laser pump – X-ray free-electron laser probe experiments and molecular-dynamics simulations. By acquiring X-ray diffraction snapshots with sub-picosecond resolution, we capture the sample's atomic structure during its transition from the crystalline to the liquid state. Bridging the timescales of experiments and simulations allows us to formulate a realistic microscopic picture of the crystal-liquid transition. According to the experimental data, the melting process gradually accelerates with the increasing density of deposited energy. The molecular dynamics simulations reveal that the transition mechanism progressively varies from heterogeneous, initiated inside the material at structurally disordered grain boundaries, to homogenous, proceeding catastrophically in the crystal volume on a picosecond timescale comparable to that of electron-phonon coupling. We demonstrate that the existing models of strongly non-equilibrium melting, developed for systems with relatively weak electron-phonon coupling, remain valid even for ultrafast heating rates achieved in femtosecond laser-excited Pd. Furthermore, we highlight the role of pre-existing and transiently generated crystal defects in the transition to the liquid state.