During recrystallization annealing of deformed metals, new strain-free crystals develop in the deformed matrix. This process is described as recrystallization nucleation. Nucleation affects the microstructure and texture and as a consequence the mechanical properties of recrystallized metals. The mechanism of recrystallization nucleation has not been fully understood although tremendous post mortem observations of nuclei have been carried out over the past decades. One of the reasons is that once a nucleus is formed in a region in the deformed matrix the deformed microstructure corresponding to that region will disappear so that the direct evidence of nucleation process is lost. In this work, we carried out in-situ electron backscatter diffraction (in-situ EBSD) study in a scanning electron microscope (SEM) to follow the microstructural and orientational evolutions during deformation and then annealing of a high purity Al sample. This means that the orientations of a given region in the sample were measured under three sample states, namely initial undeformed state, deformed state and annealed state. This type of experiments enabled us for the first time to analyze (i) the orientation change for a given region before and after the nucleation event (namely the relationship between the orientation of a newly formed nucleus and the orientation of its corresponding region in the deformed state) and (ii) the relationship between the orientation of the nucleus and the orientation of the same region in the initial undeformed state. The analysis generated new results that provide new insight into the mechanism of recrystallization nucleation. Particular attention was paid to the orientation relationships with rotation axes of <111>, which lead to a discussion on the formation mechanism of the frequently observed 40°<111> orientation relationship between nuclei and deformed matrix in fcc metals.