Hydrogen storage characteristics is studied in the Mg-alloy ZK60 after processing by different SPD (Severe Plastic Deformation) methods such as High Pressure Torsion (HPT) and Friction Stir Processing (FSP), applying various deformation extents and rates. The capacity and kinetics of hydrogen storage was investigated and analysed, up to 100 storage cycles. While the degree of SPD deformation is less important for the storage capacity, the SPD processing method itself matters, yielding about ~ 30% more capacity in FSP than in HPT. As shown by DSC and XRD analyses, it is the density of SPD-induced vacancy agglomerates which is significantly higher in FSP than in HPT (~ 10–3 instead of ~ 10–4) because of the enhanced dislocation slip activity. Thanks to their stabilization through Mg(Zn,Zr) precipitates, the vacancy agglomerates survive numerous cycles of hydrogen storage in spite of the high storage temperature of 350 °C, and can act as thermally stable heterogeneous nuclei for the hydrogenation. This latter mechanism was found in all SPD methods applied irrespective of the deformation extent, on the basis of Johnson–Mehl–Avrami-Kolmogorov analysis providing the Avrami exponent n = 1, already from the second up to the highest hydrogen storage cycles.