We present a microscopic model that successfully explains the ultrafast equilibration of magnetic order in ferromagnetic metals at a time scale tau(M) of only a few hundred femtoseconds after pulsed laser excitation. It is found that tau(M) can be directly related to the so-called Gilbert damping factor sigma that describes damping of GHz precessional motion of the magnetization vector. Independent of the spin-scattering mechanism, an appealingly simple equation relating the two key parameters via the Curie temperature T(C) is derived, tau(M) approximately c(0)h/k(B)T(C)sigma, with h and k(B) the Planck and Boltzmann constants, respectively, and the prefactor c(0) approximately 1/4). We argue that phonon-mediated spin-flip scattering may contribute significantly to the sub-ps response.