Plastic deformation and work-hardening behavior of commercially pure magnesium with a grain size between 0.8 $\mu$m - 20 $\mu$m have been studied under uniaxial tension and compression at 4K, 78K, and 298K. At room temperature, the deformation of pure Mg with a grain size above $\sim$3 $\mu$m is dominated by slip and mechanical twinning. The samples with grain size below $\sim$3 $\mu$m, in addition to slip, deform by contribution from grain boundary sliding (GBS). At the critical grain size of $\sim$3 $\mu$m and with further grain size reduction, one observes the softening of magnesium samples reflected in decreasing the yield stress and significant improvement of the plasticity. In contrast, at deformation temperatures of 78K and 4K, one observes no transition in dominant deformation modes with decreasing grain size, suggesting that GBS does not support the plastic flow of Mg samples in this temperature range. The results reveal that at cryogenic temperatures, the yield stress increases, and plasticity decreases with grain refinement. The mechanical response of studied materials will be discussed in relation to the microstructural features, texture evolution, and strain rate sensitivity results.