In this study, cryogenic temperature large strain extrusion machining (CT-LSEM) as a novel severe plastic deformation (SPD) method for producing ultra-fine grained (UFG) microstructure is investigated. Solution treated Al 7075 alloy was subjected to CT-LSEM, room temperature (RT) LSEM, as well as CT free machining (CT-FM) with different machining velocities to study their comparative effects. The microstructure evolution and mechanical properties were characterized by differential scanning calorimetry (DSC), scanning electron microscopy (SEM), transmission electron microscopy (TEM), and Vickers hardness measurements. It is observed that the hardness of the sample has increased from 105 HV to 169 HV and the chip can be fully extruded under CT-LSEM at the velocity of 5.4 m/min. The chip thickness and hardness decrease with velocity except for RT-LSEM at the machining velocity of 21.6 m/min, under which the precipitation hardening exceeds the softening effect. The constraining tool and processing temperature play a significant role in chip morphology. DSC analysis suggests that the LSEM process can accelerate the aging kinetics of the alloy. A higher dislocation density, which is due to the suppression of dynamic recovery, contributes to the CT-LSEM samples, resulting in greater hardness than the RT-LSEM samples.