The reaction of hydrogen gas with magnesium metal, which is important for hydrogen storage purposes, is enhanced significantly by the addition of catalysts such as Nb and V and by using nanostructured powders. In situ neutron diffraction on MgNb0.05 and MgV0.05 powders give a detailed insight on the magnesium and catalyst phases that exist during the various stages of hydrogen cycling. During the early stage of hydriding (and deuteriding), a MgH1 < x < 2 phase is observed, which does not occur in bulk MgH2 and, thus, appears characteristic for the small particles. The abundant H vacancies will cause this phase to have a much larger hydrogen diffusion coefficient, partly explaining the enhanced kinetics of nanostructured magnesium. It is shown that under relevant experimental conditions, the niobium catalyst is present as NbH1. Second, a hitherto unknown Mg-Nb perovskite phase could be identified that has to result from mechanical alloying of Nb and the MgO layer of the particles. Vanadium is not visible in the diffraction patterns, but electron micrographs show that the V particle size becomes very small, 2-20 nm. Nanostructuring and catalyzing the Mg enhance the adsorption speed that much that now temperature variations effectively limit the absorption speed and not, as for bulk, the slow kinetics through bulk MgH2 layers.