Recently, some researchers found that there was a notchfrequency phenomenon when the guided wave propagated in the pre-stressing strand under tension. The notch frequency has a linear relationship with the logarithm of tension. According to their results, a force measurement method for the strand was proposed. However, fatigue damage is often encountered inservice strands. In this paper, we study the effect of fatigue damage on the notch frequency of the pre-stressing strand under tension based on the magnetostrictive guided wave technology. The relationship between the cyclic loading times and the notch frequencies under the same tension is obtained from four pre-stressing strands. The results show that the notch frequencies are variable with the cyclic loading times. At first, the notch frequency increases slightly, then decreases suddenly, and then increases almost linearly with increasing of the cyclic loading times. Our research indicates that the tension measurement method by using the notch frequency for strands should consider the effect of the fatigue damage. Moreover, the notch frequency can also be employed to evaluate the fatigue damage of strands after 1.85 million cyclic loading times.