Remarkably little is known about the physical phenomena leading to nucleation of new perfect crystals within deformed metals during annealing, in particular how and where volumes with nearly perfect lattices evolve from structures filled with dislocations, and how local variations at the micrometer length scale affect this nucleation process. We present here the first experimental measurements that relate directly nucleation of recrystallization to the local deformation microstructure in the bulk of a sample of cold rolled aluminum, further deformed locally by a hardness indentation. White beam differential aperture X-ray microscopy is used for the measurements, allowing us to map a selected gauge volume in the bulk of the sample in the deformed state, then anneal the sample and map the exact same gauge volume in the annealed state. It is found that nuclei develop at sites of high stored energy and they have crystallographic orientations from those present in the deformed state. Accordingly we suggest that for each nucleus the embryonic volume arises from a structural element contained within the voxels identified with the same orientation. Possible nucleation mechanisms are discussed and the growth potentials of the nuclei are also analyzed and discussed.