Electrochemical stability is a critical performance parameter for the materials used as electrolytes and electrodes in batteries. Using first-principles electronic structure calculations, we have determined the electrochemical stability windows of magnesium binary and ternary spinel compounds. These materials are candidates for protective coatings, solid electrolytes, and cathodes in Mg batteries, which represent a promising sustainable alternative to Li-ion batteries that still dominate the battery market. Furthermore, we have applied and assessed two different criteria for the chemical stability of the compounds. For the spinel materials, we identify the critical role of the ionic radii of the transition metal for the stability of the compounds. In addition, we determine the ion mobility in these materials using a recently developed descriptor. We thus provide guidelines for the choice of promising solid materials for Mg batteries with improved properties.