The Mg-based hydrogen storage composites have been successfully prepared by mechanochemical synthesis using Ti0.32Cr0.35V0.07Fe0.26 and Ni as additives. The hydrogen sorption-desorption characteristics were mensurated by an isovolumetric method, and the structures and constitutes, and the surface and body properties were investigated by XRD, SEM, TEM, GC and XPS, respectively. The correlations of the milling time and alloy components with the structure and hydrogen sorption-desorption property were elucidated, then the hydrogen sorption-desorption mechanism was discussed. The results indicate that the hydrogen sorption-desorption temperature decreased and the kinetic properties are improved because the fine Ti0.32Cr0.35V0.07Fe0.26 and Ni particles covering magnesium matrix act as the catalytic phases to produce a significant amount of nanoparticles in favor of the decrease of temperatures and the increase of speed for hydrogen sorption-desorption.