The cold-compressed AZ31 magnesium alloys with different (2.5%, 5%, 7.5%, 10%, 12.5% and 15%) were annealed at different temperatures (573, 623 and 673K) for different time. With aid of the optical microscopy, and microhardness tester, the microstructural evolution during annealing at different temperature of the compressed AZ31 has been investigated. The microstructural characterized results were further related to the hardness test results and the calculated activation energy. The results showed that for the compressed AZ31, the recrystallization can occur on the samples with the strain just above 10% and the deformation twinning plays an important role on the nucleation and grain growth of the recrystallization. It was found that the twinning boundary was the location of the recrystallization nuclei and a lot of recrystallized grains with equiaxed shape were found along the twinning boundaries. The relationships among the nuclei orientations and the crystallographic orientations on both sides of the twining boundary have been statistically investigated. The effects of the compressed strain and the annealing temperature on annealing behavior were also discussed based on the experimental results.