The mechanisms governing the very first stage of static recrystallization in two hexagonal alloys (commercially pure titanium and low alloyed zirconium) are investigated in this paper. Initially fully recrystallized and equiaxed materials were cold-rolled to 80% thickness reduction and subsequently recrystallized at 500 degrees C for short times. High resolution EBSD maps were acquired in a FEG-SEM before and after annealing in order to see where and how the new grains appear. Nonoriented nucleation mechanisms are involved in both materials, and there is a strong correlation between the local deformation substructures and the recrystallization kinetics. Recrystallization is extremely fast in the areas where the deformation cells are small and highly misoriented, i.e. in the areas which underwent severe grain fragmentation. Twinning plays an important role for that purpose in the studied titanium sheet.