Iron-based shape memory alloys (Fe-SMAs) exhibit Shape Memory Effect (SME), allowing them to recover their previous deformation upon temperature change after pre-straining. Utilizing Fe-SMA's SME, damaged concrete structures can be prestressed-repaired by pre-straining the alloy, fixing it onto the structure surface and conducing temperature activation to generate recovering stresses within the alloy under constraint. However, under long-term cyclic loading, Fe-SMAs experience fatigue damage, accompanied by stress relaxation due to phase transformations, significantly affecting strengthening efficacy and reducing long-term fatigue performance of the strengthened structure. Traditional fatigue damage measurement methods such as strain gauges are insensitive to fatigue damage and impractical when Fe-SMAs are embedded in mortar (using near surface mounted method). This study introduces the Piezomagnetic Effect (PE) of ferromagnetic materials as a novel fatigue damage indicator for non-destructive testing of Fe-SMAs. Uniaxial cyclic tension tests were conducted on Fe-SMA standard test specimen. The magnetic field intensity and field distribution changes on the alloy surface were measured during fatigue test, and variations of the piezomagnetic signal were analyzed and compared with traditional fatigue damage indicators such as strain. Results indicate that similar to traditional fatigue damage indicators, piezomagnetic signals on Fe-SMA surfaces exhibit a three-stage trend under cyclic loading: rapid increase, steady development, and sudden change. Moreover, during different fatigue stages, changes in piezomagnetic signals are influenced by magneto-mechanical coupling, dislocation effects, and leakage magnetic effects. These findings offer new insights into fatigue damage detection in Fe-SMA strengthened concrete structures.