Magnesium batteries are considered promising solutions for future energy storage beyond the lithium-ion battery era. However, the development of magnesium batteries is hindered by the lack of suitable electrolytes. Here we present solid Mg2+ electrolytes based on ammine magnesium borohydride composites, Mg(BH4)2·xNH3, which have conductivities ca. three orders of magnitude higher than the parent compounds (x = 1, 2, 3, and 6). A nanocomposite formed by the Mg(BH4)2·xNH3 composite and MgO nanoparticles exhibits outstanding Mg2+ conductivity of the order of 10-5 S cm-1 at room temperature and around 10-3 S cm-1 at moderate temperature (ca. 70 °C), with an activation energy for Mg2+ conduction of Ea ∼108 kJ/mol (1.12 eV) and high thermal stability (Tdec = 120 °C). Characterization using solid-state nuclear magnetic resonance, powder X-ray diffraction, and transmission electron microscopy reveals that the high Mg2+ conductivity is attributed to amorphization of Mg(BH4)2·xNH3 resulting in a highly dynamic state. This nanocomposite is compatible with a Mg metal anode and allows stable Mg plating/stripping (at least 100 cycles) in a symmetric cell. The results represent a major advancement of solid-state multivalent ion conductors here demonstrated for Mg2+.