Hydrogenation of nonequilibrium alloys may form nanometer-sized metal hydride clusters, depending on the alloy compositions and hydrogenation conditions. Here in the Ti-rich compositions of the immiscible Mg-Ti system MgH2 clusters are embedded in a Ti-H matrix. Our previous works have indicated that the interface energy between the two metal hydrides reduces the stability of MgH2. The aim of our study is to obtain the structural information on the nanometer-sized clusters. Indeed, MgD2 clusters embedded in a face-centered-cubic (FCC) Ti-D matrix is found in Mg0.25Ti0.75D1.65 by means of H-2 magic angle spinning nuclear magnetic resonance (MAS NMR). The atomic pair distribution function (PDF) analysis of neutron total scattering data suggests that the MgD2 clusters have an orthorhombic structure, which is different from a rutile-type body-centered-tetragonal (BCT) structure of alpha-MgD2 observed in the Mg-rich compositions. Our results suggest that we can tune the thermodynamics of hydrogen absorption and desorption in Mg-H using the interface energy effect and accompanying stress-induced structural change, which contributes to the substantial development of lightweight and inexpensive hydrogen storage materials.