This study investigates the effect of spot overlap rate on the nanosecond pulsed laser rust removal quality of Q355B steel. Experiments were conducted with four overlap rates (0%, 20%, 40%, and 60%), and the rust removal quality was comprehensively evaluated through surface morphology observation, elemental mass fraction analysis, phase identification, chemical state characterization, roughness measurement, micro-Vickers hardness testing, and corrosion resistance assessment. The results reveal that when the spot overlap rate is increased to 40%, the rust removal quality reaches the optimum level. The rust layer is completely removed, and the surface roughness of the specimen is minimized to 2.35 μm. The micro-Vickers hardness of the treated surface (154.63 HV) is not significantly different from that of the original substrate (151.82 HV), and its corrosion resistance is superior to that of all other groups. At an overlap rate of 60%, excessive ablation on the surface of the specimen is induced due to excessive superposition of laser energy, which results in an elevated surface roughness (5.10 μm) and micro-Vickers hardness (166.3 HV), accompanied by a slight reduction in corrosion resistance. Overall, nanosecond pulsed laser rust removal with an appropriate spot overlap rate can yield a clean surface with low roughness and high corrosion resistance without impairing the mechanical properties of the Q355B steel substrate.