Bulk nanostructured magnesium alloy AZ31 has been produced by spark plasma sintering at four different temperatures from 350 to 450 °C. The effect of sintering temperature on microstructural evolution and compression behaviour was studied in detail. It was concluded that the sample consolidated at 400 °C exhibited the highest strength. Higher sintering temperature (450 °C) improved the compressive strain of the bulk sample but at the sacrifice of strength. However, samples consolidated at 350 °C displayed brittle behaviour with low strength. All consolidated samples had a bimodal microstructure with nanocrystalline and coarse grains. The nanocrystalline microstructure formed by cryomilling was retained after consolidation and a maximum microhardness was approximately 150 HV. The bulk samples consolidated at 400 °C with an average grain size of 45 nm showed exceptional average true compressive yield strength of 400.7 MPa, true ultimate compressive strength of 499.7 MPa, which was superior to published results for most of conventional magnesium alloys. Although nanostructured materials usually have high strength but poor ductility, the material in this study exhibited high strength and a true compressive strain of 0.036.