The effects of recovery on the subsequent recrystallization of tantalum were investigated via two-step annealing at two temperatures. Transmission electron microscopy, electron back-scattered diffraction, and X-ray diffraction were employed to determine the respective microstructures and textures after various annealing regimes. The results show that many large grains with {111} < uvw > orientations are developed when heating at 1573 K without pre-recovery, while pre-recovery can introduce a homogeneous fine microstructure and weaken the texture. This difference can be attributed to the recovery-induced change in nucleation mechanisms. Elongated grains stretch along grain boundaries or locate in the interior of deformed grains, mainly due to the heterogeneous distribution of stored energy. Dislocations characterized by submicron bands in the deformed state evolve into sub-grains during pre-recovery and grow continuously, indicating a homogeneous distribution of dislocation or stored energy after pre-recovery, which can significantly influence subsequent nucleation and grain growth.