The strength of traditional commercially pure titanium (CP-Ti) alloys often fails to meet the demand of structural materials. In order to enhance their mechanical properties, the cold-rolled CP-Ti alloys were annealed at different temperatures, and the recrystallization behavior and texture evolution were investigated. It was found that the bimodal microstructure (equiaxed and elongated grains) was formed after partial recrystallization, and the corresponding sample exhibited an excellent combination of ultimate tensile strength (702 MPa) and total elongation (36.4%). The recrystallization nucleation of CP-Ti sheets occurred preferentially in the high strain and the high-angle grain boundaries (HAGBs) regions. Meanwhile, the internal misorientations of the deformed heterogeneous grains increased and transformed into HAGBs, which further promoted the recrystallization nucleation. The main recrystallization texture was basal TD-split texture transformed from cold-rolled basal RD-split texture, and the oriented nucleation played a dominated role during recrystallization.