Solid-state magnesium ion conductors with exceptionally high ionic conductivity at low temperatures, 5 × 10-8 Scm-1 at 30 °C and 6 × 10-5 Scm-1 at 70 °C, are prepared by mechanochemical reaction of magnesium borohydride and ethylenediamine. The coordination complexes are crystalline, support cycling in a potential window of 1.2 V, and allow magnesium plating/stripping. While the electrochemical stability, limited by the ethylenediamine ligand, must be improved to reach competitive energy densities, our results demonstrate that partially chelated Mg2+ complexes represent a promising platform for the development of an all-solid-state magnesium battery.