Magnesium (Mg) and its alloys usually show relatively low strength and poor ductility at room temperature due to their anisotropic hexagonal close-packed (HCP) crystal structure that provides a limited number of independent slip systems. Here we report that unique combinations of strength and ductility can be realized in bulk polycrystalline pure Mg by tuning the predominant deformation mode. We succeeded in obtaining the fully recrystallized specimens of pure Mg having a wide range of average grain sizes, of which minimum grain size was 650 nm, and clarified mechanical properties and deformation mechanisms at room temperature systematically as a function of the grain size. Deformation twinning and basal slip governed plastic deformation in the conventional coarse-grained region, but twinning was suppressed when the grain size was refined down to several micro-meters. Eventually, grain boundary mediated plasticity, i.e., grain boundary sliding became dominant in the ultrafine-grained (UFG) specimen having a mean grain size smaller than 1 μm. The transition of the deformation modes led to a significant increase of tensile elongation and breakdown of Hall-Petch relationship. It was quantitatively confirmed by detailed microstructural observation and theoretical calculation that the change in strength and ductility arose from the distinct grain size dependence of the critical shear stress for activating different deformation modes.