Surface integrity of machined products can have a critical impact on their performance, such as corrosion, wear and/or fatigue resistance. It has been reported that reducing the grain size of AZ31B Mg alloys could significantly enhance its corrosion resistance, which is often the limiting factor for its wide application. Severe plastic deformation (SPD) has proved to be an effective way to induce grain refinement. In this study, the potential of cryogenic machining as a novel SPD method to induce grain refinement on the surface of AZ31B Mg alloys was investigated. The microstructures of the workpiece surface/sub-surface and the machined chips after both dry and cryogenic machining were studied. A surface layer where nanocrystallized grains exist was found in the machined surface under cryogenic conditions. Increasing the edge radius of the cutting tool resulted in a thicker grain refinement layer. In addition to the experimental study, an FE model based on the Johnson-Cook constitutive equation was developed and validated using experimental data in terms of chip morphology and forces. The capability of this model to predict critical deformation parameters for dynamic recrystallization (DRX), such as strain, strain-rate and temperature, was demonstrated. With further development, the model can be used to predict the onset of DRX and the grain size on the machined surface.