Design of new functional materials with fast Mg-ion mobility is crucial for the development of competitive solid-state magnesium batteries. Herein, we present new nanocomposites, Mg(BH4)2·1.6NH3-Al2O3, reaching a high magnesium conductivity of σ(Mg2+) = 2.5 × 10-5 S cm-1 at 22 °C assigned to favorable interfaces between amorphous state Mg(BH4)2·1.6NH3; inert and insulating Al2O3 nanoparticles; and a minor fraction of crystalline material, mainly Mg(BH4)2·2NH3. Furthermore, quasi-elastic neutron scattering reveals that the Mg2+-ion mobility in the solid state appears to be correlated to relatively slow motion of NH3 molecules rather than the fast dynamics of BH4- complexes. The nanocomposite is compatible with a metallic Mg anode and shows stable Mg2+ stripping/plating in a symmetric cell and an electrochemical stability of ∼1.2 V. The nanocomposite has high mechanical stability and ductility and is a promising Mg2+ electrolyte for future solid-state magnesium batteries.