The ultrafast dynamics of magnetic order in a ferromagnet are governed by the interplay between electronic, magnetic and lattice degrees of freedom. In order to obtain a microscopic understanding of ultrafast demagnetization, information on the response of all three subsystems is required. A consistent description of demagnetization and microscopic energy flow, however, is still missing. Here, we combine a femtosecond electron diffraction study of the ultrafast lattice response of nickel to laser excitation with ab initio calculations of the electron-phonon interaction and energy-conserving atomistic spin dynamics simulations. Our model is in agreement with the observed lattice dynamics and previously reported electron and magnetization dynamics. Our approach reveals that the spin system is the dominating heat sink in the initial few hundreds of femtoseconds and implies a transient non-thermal state of the spins. Our results provide a clear picture of the microscopic energy flow between electronic, magnetic and lattice degrees of freedom on ultrafast timescales and constitute a foundation for theoretical descriptions of demagnetization that are consistent with the dynamics of all three subsystems.