Magnesium alloys have recently attracted great interest due their lightweight and high specific strength. However, because of their hexagonal close-packed structure, they have few active slip systems, resulting in poor ductility and high mechanical anisotropy at room temperature. In the present work, we used a cross-shear deformation imposed by a differential speed rolling (DSR) technique to improve the room temperature strength and ductility of AZ31 magnesium alloy sheets. To introduce the cross-shear deformation, the sheets were rotated 180° around their longitudinal axis between the adjacent passes of DSR. The sheets of the AZ31 alloy subjected to the cross-shear deformation showed a uniform fine microstructure (1.2 ± 0.1 μm) with weak basal textures. The fabricated sheets showed a simultaneous high ultimate tensile strength and elongation-to-failure, i.e., ~333 MPa and ~21%, respectively. These were explained based on the structural features evolved due to the cross-shear deformation by DSR. The high strength was attributed to the uniform fine microstructure, whereas the high ductility was explained based on the basal texture weakening.