Nucleation in an aluminium tricrystal cold rolled along its columnar direction, to 40% thickness reduction, is studied. This experimental configuration was used to obtain the same deformation microstructure through the sample length, which made it possible to cut it into several slices of similar microstructures and use these slices differently. Some slices served to analyse the deformation microstructure and others to analyse the annealing microstructure. Nucleation developed only in one of the three crystals and not at grain boundaries. The relationship between the crystallographic orientations and the local density of nuclei and different attributes of the parent, deformation microstructure was then analysed. As generally presumed, the nuclei were observed to inherit orientations from the parent matrix. Much more surprisingly, the stored energy alone, which is often considered as the driving force for recrystallisation nucleation, was found not to provide a reliable criterion for recrystallisation nucleation in the investigated sample. Instead, the density of nuclei was the highest where the substructure is composed of sharp bands, which correspond to regions of highly anisotropic orientation distributions. A new energy criterion for recrystallisation nucleation is proposed, which is called “primary stored energy” and depends on the stored energy and the anisotropy of the orientation distribution.