We develop a generalized Langevin spin dynamics (GLSD) algorithm where both the longitudinal and transverse (rotational) degrees of freedom of atomic magnetic moments are treated as dynamic variables. This removes the fundamental limitation associated with the use of stochastic Landau-Lifshitz (sLL) equations, in which the magnitude of magnetic moments is assumed constant. A generalized Langevin spin equation of motion is shown to be equivalent to the sLL equation if the dynamics of an atomic moment vector is constrained to the surface of a sphere. A fluctuation-dissipation relation for GLSD and an expression for the dynamic spin temperature are derived using the Fokker-Planck equation. Numerical simulations, performed using ferromagnetic iron as an example, illustrate the fundamental difference between the two- and three-dimensional dynamic evolution of interacting moments, where the three-dimensional GLSD includes the treatment of both transverse and longitudinal magnetic excitations.