The hydrogenation kinetics of Mg is slow, impeding its application for mobile hydrogen storage. We demonstrate by ab initio density functional theory (DFT) calculations that the reaction path can be greatly modified by adding transition metal catalysts. Contrasting with Ti doping, a Pd dopant will result in a very small activation barrier for both dissociation of molecular hydrogen and diffusion of atomic H on the Mg surface. This new computational finding supportsfor the first time by ab initio simulationthe proposed hydrogen spillover mechanism for rationalizing experimentally observed fast hydrogenation kinetics for Pd-capped Mg materials.