AZ31 magnesium alloy sheets with different strong textures were cryorolled at the liquid-nitrogen temperature to the strain of 4% and 8%. The microstructure and texture of the rolled sheets were investigated via scanning electron microscopy (SEM), electron backscatter diffraction (EBSD), and X-ray diffraction (XRD). The mechanical properties of the sheets were tested through in-plane uniaxial tensile tests at ambient temperature. The tensile stress was exerted in the rolling direction (RD) and transverse directions (TD). The microstructural and textural evolutions of the alloy during cryorolling were investigated. Due to active twining during rolling, the initial texture significantly influenced the microstructural and textural evolutions of the rolled sheets. A {1012} extension twin was found as the dominated twin-type in the cryorolled samples. After cryogenic rolling, the ductility of the samples decreased while the strength increased. Twinning also played an important role in explaining the mechanical differences between the rolled samples with different initial textures. The samples were significantly strengthened by the high stored energy accumulated from cryorolling.