The use of carbon fiber reinforced polymer (CFRP) materials for repairing fatigue-damaged steel beams represents a viable alternative to conventional methods. With a sufficiently high Young’s modulus, CFRP materials effectively bridge local stresses across crack lips, reduce crack opening displacements, and promote crack closure. Additionally, pre-stressing CFRP strips can further decrease the fatigue crack propagation rate, potentially leading to complete crack arrest. In cracked steel beams, repaired with externally bonded (EB) CFRP strips, debonding of the composite reinforcement from the substrate is one of the main failure modes. This typically occurs within the adhesive layer (cohesive debonding) for standard adhesives, but it is not the case for toughness where interface debonding could be observed. Moreover, high stress concentrations at the crack tip can still lead to CFRP debonding, compromising the repair’s effectiveness. In this study, toughened epoxy adhesives are used to bond CFRP reinforcement in the cracked regions of fatigue-damaged steel beams. These specimens are then subjected to cyclic loading to study both the fatigue crack propagation in the steel substrate and the debonding along the interface. Results are discussed in terms of fatigue crack propagation curve in the steel beam, failure modes, reinforcement debonding and the effectiveness of the toughened adhesives when compared to standard epoxy resins.