MgH2 is a promising solid-state hydrogen storage medium with a high hydrogen capacity and low cost, but it suffers from high hydrogen sorption temperatures. In this work, Cr-doped TiO2 solid solution nanocatalysts were synthesized and demonstrated to significantly reduce the hydrogen sorption temperatures and pressure of MgH2. The Ti(5Cr)O2 catalyzed MgH2 releases over 6.1 wt % of H2 at 200 °C, and even at 175 °C, 2.62 wt % H2 can be desorbed. The dehydrogenation activation energy is greatly reduced to 85.3 ± 8.7 kJ/mol, which is ∼49.7 kJ/mol less than that observed for pure MgH2. The dehydrogenated product can absorb 4.5 wt % of H2 within 10 s at a low temperature of −20 °C and back pressure of 30 bar, or the hydrogen uptake content can reach 4.81 wt % under 5 bar and 75 °C. The mechanism study indicates that the Cr-doped TiO2 can markedly reduce the adsorption energy and dissociation energy barrier of H2 molecules and greatly enhance the dissociation ability of H on the catalyst surface. This work demonstrates the potential of modified TiO2 as a cost-effective and efficient catalyst for Mg-based hydrogen storage materials.