The effect of local microstructure on fatigue crack nucleation is investigated in an aluminum alloy 7075 by modeling polycrystals in the vicinity of cracked second phase particles.  The polycrystals are analyzed using detailed, 3D finite element models.  A crystal plasticity formulation that captures the behavior of the precipitation strengthened alloy is developed and implemented into a parallel finite element framework. First, the model is applied to an idealized grain containing a cracked ellipsoidal particle, and results for differently oriented grains are investigated.  Several different postulated crack nucleation metrics and non-local methods for computing them in the vicinity of the crack front are compared.  The evolution of the crack nucleation metrics with cycles is also studied and discussed.  Models of experimentally observed grain structures are then modeled, and the crack nucleation metrics are correlated with crack nucleation data. Finally, conclusions are drawn regarding appropriate crack nucleation metrics, non-local methods for computing them, and how they might be applied for predicting the effect of microstructure on fatigue life.