An investigation has been conducted on AZ91 magnesium alloy processed in high-pressure torsion (HPT) at 296, 423 and 473 K for different numbers of turns. The microstructure has altered significantly after processing at all processing temperatures. Extensive grain refinement has been observed in the alloy processed at 296 K with apparent grain sizes reduced down to 35 nm. Segmentation of coarse grains by twinning has been observed in the alloy processed at 423 K and 473 K with average apparent grain sizes of 180 nm and 250 nm. Substantial homogeneity in microhardness has been observed in the alloy processed at 296 K compared to that found at 423 K and 473 K. The ultrafine-grained AZ91 alloy exhibited a significant dependence of the yield strength on grain size as shown by the microhardness measurements, and it obeys the expected Hall-Petch relationship. The alloying elements, fraction of nano-sized particles of beta-phase, and the dominance of basal slip and pyramidal modes have additional effects on the strengthening of the alloy processed at 296 K.