Severe plastic deformation (SPD) has been widely employed to refine the grain size of Mg alloys, with the main objective to improve the strength and ductility of Mg alloys, since the well-known Hall-Petch equation suggests that a decreased grain size leads to an increased yield strength. However, the yield strength of Mg alloys processed by SPD is often decreased even though the grain size is effectively reduced. The abnormal flow behavior in Mg alloys processed by SPD has attracted great attention although this mechanism is still unclear, due to its complex and extensive influence factors. In this paper, the relationships between the processing conditions, grain refinement, and mechanical properties of the SPD treated Mg alloys are reviewed, with the emphasis on the effects of grain size and texture on the yield strength.