We propose a non-destructive testing methodology of estimating fatigue damage in austenitic stainless steel (prior to formation of macrocracks) that is based on monitoring changes in the effective elastic properties (more precisely, the Poisson’s ratio) due to microstructural damage. The elastic properties are also affected by growth of the martensitic phase, and the problem arises of separating the two factors. This is achieved by a combination of (1) measuring Poisson’s ratio with four-digit accuracy by ultrasonic devices, and (2) estimating volume fraction of the martensitic phase by the eddy current method. It is suggested that the critical value of the change of the Poisson’s ratio due to microstructural damage can be used as a criterion of failure.