Light weight and cheap electrolytes with fast multi-valent ion conductivity can pave the way for future high-energy density solid-state batteries, beyond the lithium-ion battery. Here we present the mechanism of Mg-ion conductivity of monoammine magnesium borohydride, Mg(BH4)2·NH3. Density functional theory calculations (DFT) reveal that the neutral molecule (NH3) in Mg(BH4)2·NH3 is exchanged between the lattice and interstitial Mg2+ facilitated by a highly flexible structure, mainly owing to a network of di-hydrogen bonds, N-Hδ+-δH-B and the versatile coordination of the BH4- ligand. DFT shows that di-hydrogen bonds in inorganic matter and hydrogen bonds in bio-materials have similar bond strengths and bond lengths. As a result of the high structural flexibiliy, the Mg-ion conductivity is dramatically improved at moderate temperature, e.g. σ(Mg2+) = 3.3 × 10-4 S cm-1 at T = 80 °C for Mg(BH4)2·NH3, which is approximately 8 orders of magnitude higher than that of Mg(BH4)2. Our results may inspire a new approach for the design and discovery of unprecedented multivalent ion conductors.