Aging steel structures are one of the common problems that structural engineers are facing today. Several studies have shown that strengthening of steel members using carbon fiber-reinforced polymer (CFRP) laminates can increase the load carrying capacity and the design fatigue life of steel members. This paper presents the results of a study on the fatigue strengthening of steel beams with bonded CFRP laminates. The principle of constant life diagram (CLD) methodology is explained. An analytical solution is developed to predict the fatigue resistance of steel beams after strengthening with bonded CFRP laminates. The method is capable to determine the required geometrical and mechanical properties of the strengthening element such that the steel detail is shifted from a finite-life regime to the infinite-life regime. In order to validate the model, five steel beams, including one reference beam and four strengthened beams were tested under cyclic loadings. The beams were strengthened with normal modulus (NM), high modulus (HM) and ultra-high modulus (UHM) laminates. It was shown that the developed analytical model can be used to choose the most effective fatigue strengthening solution.