An experimental and analytical study was conducted to investigate the fatigue behavior of tension steel plates strengthened with prestressed carbon-fiber-reinforced polymer (CFRP) laminates. A simple fracture mechanics model was proposed to predict the fatigue life of reinforced specimens. Double-edge-notched specimens were precracked by fatigue loading and then strengthened by CFRP laminates at different prestressing levels. The effects of the applied stress range, CFRP stiffness, and prestressing level on the crack growth were investigated. Experimental results show that the increase of the prestressing level extends the fatigue life of a damaged steel plate to a large amount. The CFRP with the highest prestressing level performed best, prolonging fatigue life by as much as four times under 25% higher fatigue loading. Theoretically, predicted results were in a reasonable agreement with the experimental results. A parametric analysis was also performed to investigate the effects of the applied stress range and the prestressing level on the debonding behavior of the adhesive and on the secondary crack propagation.