The Ce₅Mg₄₁ hydrogen storage alloy was ball-milled with Ni powder, leading to the formation of a structure of inlaid metallic Ni nanocrystallites dispersed throughout a Ce–Mg amorphous alloy matrix. This structure was identified to have a positive effect on improving electrochemical hydrogen storage capacity. The ball-milled Ce₅Mg₄₁ + 200 wt% Ni composite shows the highest initial discharge capacity (1046 mA h g⁻¹) and high-rate dischargeability (HRD). Electrochemical impedance spectra, cyclic voltammograms and anodic polarization measurements show that the high discharge capacity and HRD was due to high hydrogen diffusivity and low reaction resistance. With a further increase in Ni content, the discharge capacity and HRD decreases, as a result of the excessively high reaction resistance due to the presence of an excessive oxide film of Ni(OH)₂. However, the cycling stability improves with the increase of Ni content in the nanocomposite.