Grain refinement can lead to the strengthening of metallic materials according to the Hall-Petch relationship. However, our recent results suggested that grain boundary sliding is the dominant deformation mode in bulk ultrafine grained (UFG) pure Mg at room temperature, leading to softening. Here, for the first time, we report that the Hall-Petch strengthening can be regained in bulk UFG pure Mg at cryogenic temperature. At 77K, the UFG pure Mg with a mean grain size of 0.6 μm exhibited ultrahigh tensile yield strength and ultimate tensile strength of 309 MPa and 380 MPa, respectively. Combined in-situ neutron diffraction and electron microscopy investigation indicated that residual dislocation structures and deformation twins hardly formed in the UFG specimen during tensile test at 298K. In contrast, fast accumulation of lattice defects and remarkable reorientation were evident at 77K, suggesting that the grain-boundary-mediated process was suppressed and the plastic deformation was dominated by dislocation slip and deformation twinning. In addition, all the pure Mg specimens exhibited pronounced strain hardening at 77 K, which was mainly attributed to the suppressed grain boundary sliding and dynamic recovery. The mean dislocation density and relative fractions of dislocations with various Burgers vectors of the UFG specimen deformed at 77K were determined quantitatively from neutron diffraction data. Despite the strong strain hardening capacity, the UFG specimen fractured prematurely at an elongation of 5% at 77K. The significantly reduced ductility at 77K was possibly caused by its higher tensile strength, which generated high intergranular stress and resulted in intergranular fracture before reaching the point of plastic instability. Potential ways for improving the strength and ductility synergy of the UFG Mg at cryogenic temperature were proposed.