A novel hydrogen storage composite system, MgH2–Na3AlH6 (4:1), was prepared by mechanochemical milling, and its hydrogen storage properties and reaction mechanism were studied. Temperature-programmed desorption results showed that a mutual destabilization effect exists between the components. First, Na3AlH6 reacts with MgH2 to form a perovskite-type hydride, NaMgH3, Al, and H2 at a temperature of about 170 °C, which is about 55 °C lower than the decomposition temperature of as-milled Na3AlH6. Then, at a temperature of about 275 °C, the as-formed Al can destabilize MgH2 to form the intermetallic compound Mg17Al12, which is accompanied by the self-decomposition of the residual MgH2. This temperature is about 55 °C lower than the decomposition temperature for as-milled MgH2. Furthermore, when heated up to 345 °C, NaMgH3 starts to decompose into NaH, Mg, and H2, which is followed by the decomposition of NaH at a temperature of about 370 °C. Rehydrogenation processes show that Mg17Al12 and NaMgH3 are fully reversible. It is believed that the Mg17Al12 and NaMgH3 formed in situ provide synergetic thermodynamic and kinetic destabilization, leading to the dehydrogenation of MgH2, which is responsible for the distinct reduction in the operating temperatures of the as-prepared MgH2–Na3AlH6 (4:1) composite system.