In the present study, a strengthening design approach is proposed for the mixed mode I/II fatigue crack arrest in existing structural steel members using prestressed unbonded carbon fiber reinforced polymer (CFRP) composites. Through the analytical formulation of mode I and II stress intensity factor ranges, a design model is proposed to determine the strengthening solution, including the required prestressing level and/or the cross-sectional area of the reinforcement, which would ensure the complete arrest of an existing mixed mode I/II fatigue crack in a steel member. In parallel, sets of stepwise high-cycle fatigue tests were carried out on reference unstrengthened and prestressed CFRP-strengthened precracked steel plates of grade S355J2+N under various mode mixities. The experimental results revealed that the maximum tangential stress (MTS) criterion fairly predicts the state of the mixed mode I/II fatigue cracks (i.e., crack arrest or growth) in unstrengthened specimens, while the proposed design model provides a conservative estimation of the mixed mode I/II fatigue threshold in prestressed CFRP-strengthened specimens. Furthermore, the crack propagation characteristics of grade S355J2+N steel, i.e., Paris’ law parameters (C and m) and the crack closure parameter (U), were determined and demonstrated to be independent of the material rolling direction. Based on the analytical and experimental results of the current study, it can be concluded that the proposed model can be used for the safe design of strengthening solutions, which is an increasing need to extend the service life of existing fatigue-damaged steel structures; certain recommendations are provided in this regard for practical strengthening applications.