The strengthening of steel structures using externally bonded (EB) carbon fiber-reinforced polymer (CFRP) laminates has gained popularity due to the advantages such as their high strength-to-weight ratio and corrosion resistance. Even though previous studies showed the application of EB CFRP laminates can enhance the fatigue performance of cracked steel plates, little is known regarding the high-cycle fatigue performance of CFRP-to-steel bonded joints. As debonding of the CFRP laminate from the steel substrate is a commonly observed failure mode under fatigue loading, a sound understanding of the behavior of CFRP-to-steel bonded joints is crucial for a better understanding of the behavior of CFRP-strengthened cracked steel plates under fatigue loading. This study experimentally and theoretically investigates the fatigue performance of CFRP-strengthened cracked steel plates. Five pre-cracked steel plates were strengthened with CFRP laminates and tested under fatigue loading. The test results for the failure modes, the fatigue-life extension, and the behavior of the CFRP-to-steel bonded joint were discussed. A numerical modeling approach based on a recently developed bond-slip model for the behavior of the CFRP-to-steel bonded interface under fatigue loading is presented for modeling the behavior of the CFRP-strengthened cracked steel plate. Although the proposed theoretical model is conservative, this method accurately predicted the remaining fatigue life of CFRP-strengthened cracked steel plates.