In this study, CoCrFeMnNi high-entropy alloys (HEAs) with a surface gradient nanostructure were produced using industrial shot blasting, which improved their mechanical properties compared to the untreated alloy. The severely plastically deformed (SPD) surface layer had a multi-scale hierarchical structure with a high density of stacking faults, deformation nanotwins, and amorphous domains. The depth of the SPD layer steadily increased as the shot-blasting time increased. The differences in the microhardness and tensile strength before and after shot-blasting demonstrated the significant effect of the SPD layer on the mechanical performance. The microhardness of the homogenized HEA was similar to 5 GPa. In comparison, the maximum microhardness of the specimens after 20 min of shot blasting was similar to 8.0 GPa at the surface. The yield strength also improved by 178%, and a large ductility of similar to 36% was retained. Additional nanograin boundary, stacking fault, and twin strengthening within the gradient-nanostructured surface layer caused the strength to increase. During tensile deformation, strain concentration began at the surface of the specimen and gradually spread to the interior. Thus, the gradient-nanostructured surface layer with improved strain hardening can prevent early necking and ensure steady plastic deformation so that high toughness is achieved.