Magnesium transition-metal alloys have a high hydrogen-storage capacity and show improved hydrogen-uptake and -release kinetics compared to magnesium alone. In the present study we have investigated the structure of bulk magnesium-titanium deuteride Mg0.65Ti0.35Dx prepared via mechanical alloying and gas-phase deuterium absorption by combined use of x-ray diffraction (XRD), neutron diffraction, and magic-angle-spinning 2H nuclear magnetic resonance (NMR). The initial ball-milled alloy has two XRD-distinct Mg and Ti fcc phases. Even after prolonged exposure to deuterium gas at 75 bar and 175 °C the materials with and without palladium catalyst are only partly deuterated. Deuterium loading causes the formation of, on the one hand, bct (rutile) MgD2 nanodomains with interdispersed TiDy layers and, on the other hand, a separate fcc (fluorite) TiDz phase. The TiDy phase is XRD invisible, but shows clearly up at a 2H NMR shift of −43 ppm between the shift of MgD2 (3 ppm) and the Knight shift of the TiDz phase (−143 ppm). Exchange NMR indicates complete deuterium exchange at 25 °C between the MgD2 and TiDy phase within 1 s, as consistent with intimate contacts between these phases. Combined analysis of the XRD and NMR peak areas suggests that the deuterium concentrations y and z in the TiDy and TiDz domains are about 1.5 and 2.0, respectively. Comparing the intrinsic cell parameters of rutile MgH2 and fluorite TiH2, we propose that stabilization of the mixed nanocomposite may arise from a coherent coupling between the crystal structures of the rutile MgD2 nanodomains and the thin layers of fcc TiDy.