In this work, we examined the influence of microstructural changes, such as an intermetallic sigma (σ) phase, on the fatigue behavior of high-temperature aged AISI 316L stainless steel. Nondestructive ultrasonic test and fatigue crack growth tests were performed to determine the threshold stress intensity factor of these artificially aged specimens. Ultrasonic test results characterizing the microstructural changes were compared with those of the fatigue tests to propose an empirical formula capable of predicting the threshold stress intensity factor by a nondestructive method. We observed a strong correlation between the increase in the volume fraction of the σ phase and the decrease of ΔKth. Ultrasonic velocity increased in response to the coarsening behavior of the σ phase in the vicinity of the grain boundaries.