Fatigue behavior is intrinsically linked to microstructural alterations induced by cyclic loading. However, the quantification of microstructural defects associated with fatigue damage of NiTi shape memory alloys (SMAs) is lacking, which hinders the development of a physically based fatigue criterion. To this end, a multi-scale experimental analysis was conducted on cyclically deformed NiTi SMAs, which evidenced a strong correlation between microstructural inhomogeneity and localized deformation behavior. The microstructural change associated with fatigue was quantified in terms of stored strain–energy, with the highest values observed in the regions where fatigue cracks initiate. Consequently, stored energy is deemed as an effective fatigue indicator, offering valuable insights for future work in the design and optimization of SMAs’ structures against fatigue.