Nanocrystalline metallic materials prepared by severe plastic deformation often possess high strength but low ductility due to the low dislocation accumulation capacity of the nanograins. Here, we report a unique process, namely, cryogenic laser shock peening (CLSP), to generate gradient nanotwinned microstructure that leads to high strength while preserving the ductility. It was observed that gradient structure was generated in copper. Near the top surface, nanocrystalline with high dense nanotwins have been observed; with the depth increasing, the fraction of the twin boundaries reduces and more heavily dislocated subgrains are observed. It has been demonstrated that CLSP can significantly improve material strength while preserving the ductility.The mechanism of the formation of gradient microstructure and high dense nanotwins near the surface was discussed. The reason behind the improvement in strength and ductility was investigated.