Increased efficiency and improved performance associated with light-weight materials were investigated in this study. Numerous studies have investigated surface treatments to improve the fatigue strength of metals. Laser heat treatment is a promising method because the power and spot size can be easily controlled, allowing a small heat affected zone (HAZ). However, changes in the material properties can result; in particular, the material can become more brittle. In this study, a combination of laser heat treatment and vibration peening was proposed to increase fatigue strength without changing the material characteristics. SCM440H was investigated experimentally, and specimens were tested using a giga-cycle ultrasonic fatigue tester. The results show that the combination of these two processes significantly increased the fatigue strength and, furthermore, different fracture types were observed after a small and large number of cycles.