Stainless steel is used in many applications because of its excellent mechanical properties at elevated temperatures. Material fatigue is a major problem in steel structures and can cause catastrophic damage resulting in significant economic consequences. Conventional nondestructive evaluation techniques can detect macro defects but do not perform well when it comes to material degradation due to fatigue, which happens at a microstructure level. It is well known that stress applied on a material will have an impact on the microstructure and produces a change in the magnetic properties of the material. Hence, magnetic nondestructive evaluation techniques that are sensitive to changes in magnetic properties play a major role in the early-stage fatigue detection, i.e., before the macro crack initiates. This paper introduces the magnetic Barkhausen noise technique to garner information about fatigue state of the material under test. K-medoids clustering algorithm and genetic optimization algorithm are used to classify the stainless-samples into fatigue categories. The results prove that martensitic grade stainless-steel samples in different stages of fatigue can be classified into broad fatigue categories, i.e., low fatigue, mid fatigue, and high fatigue based on the remaining useful life of the sample.