This paper reports a study on nanostructured magnesium composites with carbon nanotubes (CNTs) and catalytic transition metals with high H2 adsorption capacity and fast adsorption kinetics at reduced hydrogenation temperatures. Nanostructures in such a composite are shown to be responsible for improvements in both adsorption capacity and kinetics. It is found that the carbon nanotubes significantly increase the hydrogen storage capacity, and the catalytic transition metals (Fe and Ti) greatly improve the kinetics. This could be understood from the enhancement of diffusion by CNTs and decrease in energy barrier of hydrogen dissociation at the magnesium surface.