Embodiments of a solid-state electrolyte comprising magnesium borohydride, polyethylene oxide, and optionally a Group IIA or transition metal oxide are disclosed. The solid-state electrolyte may be a thin film comprising a dispersion of magnesium borohydride and magnesium oxide nanoparticles in polyethylene oxide. Rechargeable magnesium batteries including the disclosed solid-state electrolyte may have a coulombic efficiency ≧95% and exhibit cycling stability for at least 50 cycles.