Eddy current testing is commonly applied on austenitic stainless steel. 304 austenitic stainless steel always deforms during the process of manufacture or in service. The undesired deformation creates ferrite and martensite which causes a change of permeability. In that case, the non-magnetic austenitic stainless steel turns to be ferromagnetic. Thus, the needed eddy current testing frequency needs to be changed too. Experimental results show that when the deformation of 304 stainless steel specimens is less than 20%, the permeability of specimens increased and shown magnetic properties of ferromagnetic materials. Therefore, the skin depth of eddy current testing decreases and the optimal excitation frequency is no longer the best. The eddy current signal characteristics with different frequency had been studied which got from austenitic stainless steel specimen with a groove. The result shows that the best testing frequency varies with content of martensite. This paper discusses the algorithm of acquiring optimal testing frequency and demonstrates the frequency range can be achieved in the limited deformed range.