This study was conducted to determine whether the different residual stresses caused by different welding speeds affect the static and fatigue strength of laser-welded lap joints. Residual stresses in STS301L laser-welded lap joints of different thicknesses under two laser-welding speed conditions, 4.1 m/min and 5.1 m/min, were evaluated with the incremental hole-drilling strain gage method at the middle of the heat-affected zone (HAZ). Then, static and fatigue tests were performed. The results show that higher static and fatigue strengths were obtained from the specimens welded with a 4.1 m/min welding speed than from the specimens welded at 5.1 m/min. The main difference was due to the compressive principal residual stress magnitude and its orientation near the HAZ. Also, the micro-hardness profile along the failure interface was measured to verify the static and fatigue failure behavior.