The effects of different strain levels applied through high-pressure torsion (HPT) deformation following annealing on the microstructural evolution, thermal stability, and mechanical properties of Al-4Mg-0.3Cu alloy were investigated. The results reveal that Cu-segregated grain boundaries (GBs) were generated in the ultrafine-grained Al-4Mg-0.3Cu alloy with high angle grain boundaries. By contrast, the phenomenon of Cu segregation was not found in micron-scale and submicron-scale grains with low-angle grain boundaries. The mechanism of Cu segregation in ultrafine-grained Al-4Mg-0.3Cu alloy was discussed. After heat treatment, Cu segregation induced the precipitation of the dense Al2CuMg phase at GBs, which strongly inhibit grain growth and improve thermal stability. Stress–strain curves of as-cast, 5-turn, and 10-turn HPT samples showed that fracture strength significantly increased, attributed to grain size refinement, dislocation density increase, and Cu segregation at GBs. After heat treatment, 5-turn and 10-turn HPT samples demonstrate an enhanced elongation to fracture with a slight reduction of fracture strength.