There is a significant number of old metallic bridges with high levels of structural degradation due to their long service period. Fatigue problems are especially important in these structures since the majority of them were not designed taking into account this phenomenon. Several investigations showed that riveted joints are critical details since several fatigue cracks were found in these joints. In this sense, strengthening methodologies need to be studied. The strategy that has been considered a good solution is the implementation of injection bolts to replace faulty rivets. The structural performance of injection bolts has been demonstrated essentially under quasi-static conditions presenting good results. This paper intends to contribute to the scientific knowledge regarding the fatigue behavior of connections with preloaded injection bolts in the context of a bridge strengthening scenario. An experimental investigation was conducted to compare the fatigue performance of connections with preloaded injection bolts and preloaded standard bolts. Single and double shear connections were tested. New S–N design curves were proposed based on a statistical analysis of the results and compared with the S–N curves proposed in EC3-1–9. The obtained results showed that the use of injection bolts lead to lower scatter and improvement of fatigue life. It was verified that the Eurocode 3 is not able to represent the fatigue strength of connections whose performance is influenced by old metallic materials. Additionally, the fatigue behavior of these connections was assessed by numerical analysis. The relevance of the fatigue crack initiation was evident.