In this study, the effect of baking heat treatment on fatigue strength and fatigue life was evaluated by performing baking heat treatment after shot peening treatment on 4340M steel for landing gear. An ultrasonic fatigue test was performed to obtain the S–N curve, and the fatigue strength and fatigue life were compared. The micro hardness of shot peening showed a maximum at a hardened depth of about 50 μm and was almost uniform when it arrived at the hardened depth of about 400 μm. The overall average tensile strength after the baking heat treatment was lowered by about 80–111 MPa, but the yield strength was improved by about 206–262 MPa. The five cases of specimens showed similar fatigue strength and fatigue life in high cycle fatigue (HCF) regime. However, the fatigue limit of the baking heat treated specimens showed an increasing tendency rather than that of shot peening specimens when the fatigue life was extended to the very high cycle fatigue (VHCF) regime. The effect of baking heat treatment was identified from improved fatigue limit when baking heat was used to treat the specimen treated by shot peening containing inclusions. The optimum temperature range for the better baking heat treatment effect could be constrained not to exceed maximum 246 °C.