Microscopic and sample-scale heterogeneities have been characterized in nickel processed by accumulative roll bonding (ARB) to a von Mises strain of 4.8, and their influence on recrystallization have been analyzed. The microscopic deformation heterogeneities in this material are mostly associated with regions near the bonding interface, which are more refined and thus possess a higher stored energy than other regions. These regions also contain characteristic particle deformation zones around fragments of the steel wire brush used to prepare the surface for bonding. The sample-scale heterogeneities are seen as variations in the distribution of different texture components and in the fractions of high misorientation regions between the subsurface, intermediate, and central layers. Each of these heterogeneities affects the progress of recrystallization. Regions near bonding interfaces and particle deformation zones are found to act as preferential nucleation sites. Preferential nucleation is also observed at shear bands and within cube-oriented lamellae. On the sample scale, recrystallization proceeds faster in the intermediate layer than in the central and subsurface layers.