As economically viable alternatives to lithium-ion batteries, magnesium-ion-based all-solid-state batteries have been researched to meet the criteria for an ideal energy storage device. With an energy-dense magnesium-metal anode, such batteries can provide almost double the volumetric energy density at half the cost when compared with that obtainable from the state-of-the-art lithium-ion batteries. Although the development of solid-state magnesium-based batteries is hindered by various factors, the identification of an appropriate electrolyte remains the most challenging and limiting factor. In this review, we provide a survey of inorganic ceramic, metal–organic framework, glass, and organic solid polymer electrolytes that have been developed till date. We discuss the relationship between the structure, composition, and ionic conductivity of these inorganic Mg²⁺-ion solid-state electrolytes as well as the fundamental Mg-ion conduction mechanisms that govern magnesium transport in these solids, emphasizing on Mg²⁺-ion-conducting inorganic materials. By a comparison of Mg²⁺- and Na⁺-ion conductors under the theoretical framework of multi-excitation entropy (or Meyer–Neldel rules), we highlight the possible differences between these two systems, which can yield substantially different ion transport characteristics.