A high-energy ball milling and subsequent high-pressure torsion method was applied to synthesize nanocrystalline magnesium samples catalyzed by TiO2 or titanate nanotubes. The microstructure of the as-milled powders and the torqued bulk disks was characterized by X-ray diffraction. The recorded diffractograms have been evaluated by the convolutional multiple whole profile fitting algorithm, which provided microstructural parameters (average crystal size, crystallite size distribution, average dislocation density). The morphology of the nanotube-containing disks has been examined by high-resolution transmission electron microscopy. The effect of the different additives and preparation conditions on the hydrogen absorption behavior was investigated in a Sieverts’-type apparatus. It was found that the ball-milling route has a prominent effect on the dispersion and morphology of the titanate nanotubes, and the absorption capability of the Mg-based composite is highly dependent on these features.