Experimental observations of the ultrafast (less than 50 fs) demagnetization of Ni have so far defied theoretical explanations particularly since its spin-flipping time is much less than that resulting from spin-orbit and electron-lattice interactions. Through the application of an approach that benefits from spin-flip time-dependent density-functional theory and dynamical mean-field theory, we show that proper inclusion of electron correlations and memory (time-dependence of electron-electron interaction) effects leads to demagnetization at the femtosecond scale, in good agreement with experimental observations. Furthermore, our calculations reveal that this ultrafast demagnetization results mainly from spin-flip transitions from occupied to unoccupied orbitals implying a dynamical reduction of exchange splitting. These conclusions are found to be valid for a wide range of laser pulse amplitudes. They also pave the way for ab initio investigations of ultrafast charge and spin dynamics in a variety of quantum materials in which electron correlations may play a definitive role.