Poor corrosion resistance is one of the major disadvantages of magnesium alloys that inhibits their wide application. It was reported frequently that the alloys' microstructure has a significant influence on their corrosion resistance. In this study, cryogenic machining is used as a severe plastic deformation tool to modify the surface and subsurface microstructures of an AZ31 Mg alloy. Liquid nitrogen is applied to suppress grain growth caused by large heat generation during machining. "White layers", where grain boundaries were invisible, were shown to form on the surface and subsurface after machining. The hardness of this layer was about 60% larger than the bulk material. The tool edge radius and the cutting speed have profound influence on the microstructures. Preliminary results from immersion tests in simulated body fluid showed that the corrosion resistance of the AZ31 Mg alloy was enhanced due to the formation of white layer.