At finite temperatures lattice vibrations and magnetic fluctuations are coexisting. To study potential coupling effects, a method is required, which considers both, the spin and the lattice degrees of freedom, simultaneously. We develop and implement such a method by combining atomistic spin dynamics with ab initio molecular dynamics.