The rapid growth of portable consumer electronics and electric vehicles demands new battery technologies with greater energy stored at a reduced cost. Energy storage solutions based on multivalent metals, such as Mg, could significantly increase the energy density as compared to lithium-ion based technology. In this paper, we employ density functional theory calculations to systematically evaluate the performance, such as thermodynamic stability, ion diffusivity and voltage, of a group of 3d transition-metal sulfur-spinel compounds (21 in total) for multivalent cathode applications. Based on our calculations, Cr2S4, Ti2S4 and Mn2S4</sub spinel compounds exhibit improved Mg2+ mobility (diffusion activation energy <650 meV) relative to their oxide counterparts, however the improved mobility comes at the expense of lower voltage and thereby lower theoretical specific energy. Ca2+ intercalating into Cr2S4 spinel exhibits a low diffusion activation barrier of 500 meV and a voltage of ∼2 V, revealing a potential cathode for use in Ca rechargeable batteries.