A detailed structural analysis of Mg-Ti-H thin films reveals the presence of a chemically partially segregated but structurally coherent metastable phase. By combining X-Ray Diffraction and Extended X-ray Absorption Fine Structure (EXAFS) spectroscopy on MgyTi1-yHx thin films we find non-zero Chemical Short-Range Order (CSRO) parameters for all the compositions measured. Despite the positive enthalpy of mixing of Mg and Ti the degree of ordering does not increase upon loading and unloading with hydrogen. The robustness of this system and the fast and reversible kinetics of hydrogen loading and unloading are caused by the formation of nanoscale compositional modulations in the intermetallic alloy. This microstructure is responsible for the exceptional properties of MgyTi1-yHx thin films. It also shows that reversible metastable metal-hydrides offer new possibilities for hydrogen storage, beyond the limits imposed by thermodynamic equilibrium.