In this Letter, we provide a microscopic model for the ultrafast remagnetization of atomic moments already quenched above the Stoner-Curie temperature by a strong laser fluence. Combining first-principles density functional theory, atomistic spin dynamics utilizing the Landau-Lifshitz-Gilbert equation, and a three-temperature model, we analyze the temporal evolution of atomic moments as well as the macroscopic magnetization of bcc Fe and hcp Co covering a broad time scale, ranging from femtoseconds to picoseconds. Our simulations show a variety of complex temporal behavior of the magnetic properties resulting from an interplay between electron, spin, and lattice subsystems, which causes an intricate time evolution of the atomic moment, where longitudinal and transversal fluctuations result in a macrospin moment that evolves highly nonmonotonically.