Cyclic deformation and fatigue behavior of an iron-based shape memory alloy (Fe-SMA) Fe-17Mn-5Si-10Cr-4Ni-1(V,C) were studied. In the first step, cyclic tensile tests were performed to characterize the material's mechanical properties in tension (elongation at break, yield, and tensile strength) as well as the recovery behavior of the alloy. Furthermore, the effect of strain rate on the cyclic loading tests was investigated. It was observed that the strain rate has a clear influence on the stress-strain behavior of the alloy. In the second step, the fatigue behavior of the alloy after pre-straining and thermal activation under strain-controlled conditions was evaluated. While the stiffness of the alloy remained almost constant during high-cycle fatigue loading, a decrease in the recovery stress was observed, which should be taken into account in design assessments. The loss in the recovery stress was assumed to be mainly a result of a transformation-induced relaxation (TIR) under cyclic loading. Furthermore, this study examines the applicability of a constant life diagram (CLD) model to determine the fatigue limit of the alloy for different stress ratios (R). The existing results of the fatigue tests showed full consistency with the proposed fatigue design criterion. A formulation based on the CLD model was proposed for a safe design of the alloy as a structural pre-stressing element under a high-cycle fatigue loading regime.