Fatigue crack nucleation at a non-metallic agglomerate inclusion has been studied by high spatial resolution Digital Image Correlation (HR-DIC) and high angular resolution Electron Backscatter Diffraction (HR-EBSD). Spatial and temporal characterization and correlation of deformation with underlying microstructures has been performed, with distributions of plastic strain measured from HR-DIC; and residual stress and density of geometrically necessary dislocations (GND) measured from HR-EBSD. Initial residual stress and GND fields, as a consequence of differing thermal expansivities in the metallic and oxide phases, localized around the agglomerate have been quantified using HR-EBSD. The localization of the pre-existing stress and dislocation states appear to lead to early onset of plasticity upon subsequent mechanical loading. Heterogeneous distributions of plastic strain have been observed in the course of the fatigue test by HR-DIC. Crack nucleation via agglomerate/nickel interface decohesion and particle fracture has been demonstrated and this is correlated with the elevation in strain and dislocation density. The measurements of residual stress, strain, and dislocation density provide key information for the mechanisms of fatigue cracking and the development of damage nucleation criteria in these material systems.