Because both nucleation and growth are local phenomena, recrystallization depends on the spatial distribution of strains in a plastically deformed polycrystal. Using a polycrystal plasticity finite element model, we calculated these distributions for equiaxed polycrystals of copper with a random texture. We incorporated the results into a mesoscale recrystallization simulation with a nucleation model based on subgrain evolution. The coupled simulation results indicate that differences in local structure cause significant differences in recrystallization kinetics and grain size distribution. Furthermore, recrystallization in non-uniformly deformed polycrystals, even those with a random texture, is quantitatively and qualitatively different than predicted by continuum models that assume a uniform distribution of strains. This work highlights the need to examine all length scales relevant to the recrystallization process.