Grain refinement taking place in a magnesium alloy AZ31 was studied in a single- and multi-directional compression at a temperature of 573K. The structural changes observed by SEM/EBSD analysis can be characterized by the evolution of many mutually crossing kink bands at low strains, continuous increase in their number and misorientation angle in moderate strain and finally full formation of a fine-grained structure in high strain. The characteristics of new grain evolution process are sensitively affected by initial grain size (D0) and strain path. New grains are developed faster with decrease in D0. Multi-directional compression accelerates the evolution of fine grains and the improvement of plastic workability. The mechanism of new grain formation is discussed in detail.