Fatigue damage in polycrystalline metals is largely governed by the microstructural details, including crystallographic orientation, misorientation, and microtexture of the materials. These features influence fatigue crack initiation and propagation by producing the stress gradient at the interface of the hard and soft grains containing the dislocation pile-ups. In the first part of this chapter, the importance of microstructure on the cyclic deformation is reviewed in detail. The understanding of microstructure in determining minimum fatigue properties can assist the design of the appropriate processing schedules for life management of legacy systems. The elimination of microstructural variation by suitable processing can reduce scatter in fatigue performance plots. The next part of the chapter shows a specific example with the use of electron back-scattered diffraction (EBSD) and electron channeling contrast imaging (ECCI) to study the change of the microstructure, microtexture, and dislocation structure following cyclic deformation of a 304 LN austenitic stainless steel using a strain amplitude of 0.5%. The increase in the fraction of low-angle grain boundaries (LAGB) with the cyclic life is associated with the decrease in the fraction of high-angle boundaries (HAGB) and twin boundaries. The geometrically necessary dislocation (GND) density changes linearly for varying life fractions in the cyclically stable region suggesting a change of back stress. The GND storage is influenced by the size and orientation of the austenite grains. The GND density is maximum in {111} < 0–11 > grains with the highest Taylor factor.