In order to improve the fatigue resistance of orthotropic steel decks (OSDs), the steel bridge deck was annealed to reduce the welding residual stress of key welds. This work at first presented a systematical review and discussion over the distribution pattern of welding residual stress in OSDs, in accordance with a conceptual analysis respecting the impact of residual stress on fatigue crack propagation. Then, the associated summarization and comparison were made on the common approaches to mitigate the welding residual stress in the worldwide. By referring to the manufacturing of pressure vessels, the authors suggested to reduce welding residual stress by introducing annealing treatment to OSDs. On this basis, the study focused on the rib-to-deck welded joints that demonstrates a relatively prominent fatigue issue. The residual stress measurements and fatigue tests were carried out using a total of sixteen full-scale specimens, i.e., nine annealed specimens and seven as-welded ones without any additional treatment. The test results showed a reduction in the residual stress of welded joint in OSDs by 80% after the annealing, and moreover, an enhancement in the fatigue strength by 23%. Obviously, the annealing can significantly reduce the residual stress of the weld joints and effectively improve the fatigue resistance of OSDs.