We present the magnetic Moment Tensor Potentials (mMTPs), a class of machine-learning interatomic potentials, accurately reproducing both vibrational and magnetic degrees of freedom as provided, e.g., from first-principles calculations. The accuracy is achieved by a two-step minimization scheme that coarse-grains the atomic and the spin space. The performance of the mMTPs is demonstrated for the prototype magnetic system bcc iron, with applications to phonon calculations for different magnetic states, and molecular-dynamics simulations with fluctuating magnetic moments.