Laser shock peening—a very promising life enhancement technique—has demonstrated great success regarding the improvement of fatigue behavior via deep compressive residual stresses. However, the prediction and adaption of residual stress fields on basis of the laser peening parameters are still not comprehensively established. The aim of the current work is to investigate the effects of the laser pulse energy, the number of treatment overlaps as well as the laser spot size on the resulting residual stress distribution, characterized by following quantities: the residual stress close to the surface, the maximum compressive residual stress, and the integral compressive stress area over the specimen depth. For a systematic investigation of all main and interaction-based process parameter effects, and a subsequent parameter optimization, the general full factorial design is employed. The results show that laser shock peening with different process parameter combinations, inducing residual stresses with comparable integral stress area, can lead to a minimum fatigue life extension of approx. 100,000 cycles, representing a minimum fatigue life of 250% of the base material. The experimental scatter in the number of cycles to failure follows the Weibull distribution which qualitatively correlates with the standard deviation of the integral stress area.