We present a computationally efficient general first-principles based method for spin-lattice simulations for solids. Our method is based on a combination of atomistic spin dynamics and molecular dynamics, expressed through a spin-lattice Hamiltonian where the bilinear magnetic term is expanded to second order in displacement, and all parameters are computed using density functional theory. The effect of first-order spin-lattice coupling on the magnon and phonon dispersion in bcc Fe is reported as an example, and is seen to be in good agreement with previous simulations performed with an empirical potential approach. In addition, we also illustrate the abilities of our method on a more conceptual level, by exploring dissipation-free spin and lattice motion in small magnetic clusters (a dimer, trimer and quadmer). Our method opens the door for quantitative description and understanding of the microscopic origin of many fundamental phenomena of contemporary interest, such as ultrafast demagnetization, magnetocalorics, and spincaloritronics.