Practical, structure-preserving methods for integrating classical Heisenberg spin systems are discussed. Two new integrators are derived and compared, including (1) a symmetric energy and spin-length preserving integrator based on a Red-Black splitting of the spin sites combined with a staggered timestepping scheme and (2) a (Lie-Poisson) symplectic integrator based on Hamiltonian splitting. The methods are applied to both 1D and 2D lattice models and are compared with the commonly used explicit Runge-Kutta, projected Runge-Kutta, and implicit midpoint schemes on the bases of accuracy, conservation of invariants and computational expense. It is shown that while any of the symmetry-preserving schemes improves the integration of the dynamics of solitons or vortex pairs compared to Runge-Kutta or projected Runge Kutta methods, the staggered Red-Black scheme is far more efficient than the other alternatives. (C) 1997 Academic Press.