An Al-Cu-Li alloy was selected as the model material to get insight into the mechanism of deformation strengthening at cryogenic temperatures. The mechanical properties and microstructure evolution of the alloy fabricated by symmetric rolling and asymmetric rolling (the rolling ratio was 1.3) at different temperatures (25 °C, − 100 °C, − 190 °C) were investigated. Smaller grains and denser dislocations were observed in the cryorolled samples, leading to strength enhancement compared to the samples processed at room temperature. The heterogeneous grain structure was made of coarse and fine grains in the samples processed by cryorolling (CR) at − 100 °C, which resulted in higher strength and better ductility than those processed by CR at − 190 °C and room temperature rolling. Finally, a new back stress model was employed to calculate the yield strength of the heterogeneous structure, which could explain the highest strength of samples processed by CR at − 100 °C.