The paper discusses the application of an iron-based shape memory alloy (Fe-SMA) for the fatigue strengthening of steel plates. The shape memory effect (SME), which is the characteristic behavior of the Fe-SMAs, was used for the prestressed strengthening of steel plates. One steel plate without any pre-cracks and two steel plates with pre-cracks were retrofitted with Fe-SMA strips. The SMA-strengthened specimens along with a reference unstrengthened specimen were then subjected to high cycle fatigue (HCF) loading. The effect of multiple re-activations and different loading frequencies (e.g., f_r = 0.005, 5, 10, and 15 Hz) on the HCF behavior of the Fe-SMA was investigated. The test results showed that the achieved prestressing level (i.e., recovery stress) in the Fe-SMAs for an activation temperature of 260 °C was in the range of 330–410 MPa, resulting in compressive stresses in the range of 35–72 MPa in the steel plates. Furthermore, it was observed that the recovery stress decreases slightly during cyclic loading, which should be considered in the design. The loss in the prestressing level was approximately 17–20% of the original prestressing; however, the re-activation (i.e., a second activation) process could retrieve a significant portion of the loss. The test results showed that the activated Fe-SMA strips could apply considerable compressive stresses to the cracked steel plate, which reduce the tensile stresses and stress intensity factors (SIFs) at the vicinity of the crack tip, resulting in a significant increase in the fatigue life of the specimens and a complete fatigue crack arrest in some cases.