Tension–tension fatigue tests of notched 18CrNi4A steel specimens were carried out under three different fatigue stresses, and metal magnetic memory (MMM) signals were detected. The effects of fatigue damage and fatigue stress on MMM signals were investigated. The results show that the absolute values of the feature parameters Hp(y)max, Hp(y)min and Hp(y)sub increase with the aggravation of the fatigue damage. There is an inherent relationship between the fatigue stress and the values of the Hp(y)sub; the larger the fatigue stress is, the larger the absolute values of the Hp(y)sub is. Fatigue-damaged locations can be effectively predicated according to the mutational character of the Hp(y) curve and the K curve, and zero-crossing points of the Hp(y) curve, respectively. Fatigue damage degree can be effectively predicated according to the value of the Kmax and the Hp(y)max, Hp(y)min and Hp(y)sub.