The introduction of carbon fiber reinforced polymer (CFRP) with higher Young’s modulus has broadened its application to the strengthening of steel structures, especially under fatigue loading. Most research on CFRP strengthening of steel under fatigue loading has focused on tension fatigue testing, assuming that cracks or crack-like defects propagate in pure tension mode. However, the complex details and welded connections in aging metallic structures may contain cracks orientated randomly with respect to the loading direction. This paper aims to extend the current knowledge of CFRP strengthening of steel elements in tensile fatigue loading to the case of mixed tension and shear loading. Steel plates were artificially cracked from a central hole at six different angles (10°–90°) with respect to the loading axis. Each crack angle represents a certain degree of mode mixity. Ultra-high modulus CFRP was used for strengthening in this study. Twelve specimens were strengthened with two CFRP patching configurations. Six unrepaired specimens were tested to act as control specimens. A shifting phenomenon was identified to describe the influence of mixed mode in terms of crack propagation. A mixed mode modification factor was developed to estimate the fatigue life of CFRP-strengthened steel plates with inclined initial cracks.