Mg nanoparticles with metal-oxide core-shell morphology were synthesized by inert-gas condensation and decorated by in situ Pd deposition. Transmission electron microscopy and x-ray diffraction underline the formation of a noncontinuous layer with Pd clusters on top of the MgO shell. Even in the presence of a thick MgO interlayer, a modest (2 at. %) Pd decoration deeply enhances the hydrogen sorption properties: previously inert nanoparticles exhibit metal-hydride transformation with fast kinetics and gravimetric capacity above 5 wt %.