In polycrystalline metals, microstructural features such as grain boundaries (GBs) influence fatigue crack initiation. Stress and strain heterogeneities, which arise in the vicinity of GBs, can promote the nucleation of fatigue cracks. Because of variations in grain size and GB types, and consequently variations in the local deformation response, scatter in fatigue life is expected. A deeper quantitative understanding of the early stages of fatigue crack nucleation and the scatter in life requires experimental and modelling work at appropriate length scales. In this work, experiments are conducted on Hastelloy X under fatigue conditions, and observations of fatigue damage are reported in conjunction with measurements of local strains using digital image correlation. We use a recent novel fatigue model based on persistent slip band-GB interaction to investigate the scatter in fatigue lives and shed light into the critical types of GBs that nucleate cracks. Experimental tools and methodologies, utilizing ex situ digital image correlation and electron backscatter diffraction, for high resolution deformation measurements at the grain level are also discussed in this paper and related to the simulations.