The static-annealing behavior and evolution of the microstructure-strength relationship of severely-deformed commercial-purity titanium Grade 4 over the temperature range of 50–850 °C (0.16–0.57 Tm, where Tm is the melting point) were established. The severely-deformed material was obtained via equal-channel angular pressing (ECAP) using the Conform (ECAP-C) technique at 200 °C to an effective accumulated true strain of 8.4. The resulting ultrafine structure was stable to 400 °C. The excellent thermal stability was concluded to be associated with a strain-aging effect, i.e., the enhanced diffusion of solutes within this temperature interval resulting in the formation of solute atmospheres at/near dislocations. At 450–500 °C, rapid growth of strain-free grains occurred, which eliminated the severely-deformed microstructure and promoted softening. This process was deduced to be controlled primarily by grain-boundary energy and therefore was interpreted primarily in terms of grain growth rather than discontinuous recrystallization expected in this temperature range. A further increase in annealing temperature to 600 °C led to normal grain growth. Analysis of the microstructure-strength relationship suggested a significant influence of mechanical twinning on yield strength of the fully-annealed material. At 600 °C and higher temperatures, dissolution of constituent iron-rich particles was observed. This promoted a partial α → β transformation at the temperatures noticeably below the typical beta-transus of pure titanium (~880 °C). This phenomenon resulted in the precipitation of nanoscale β particles which imparted substantial strengthening. Water quenching of the material annealed at 850 °C gave rise to a β → α′ martensitic transformation. The latter process was governed by exceptionally strong variant selection and thereby provided a nearly-ideal restoration of crystallographic orientations of parent α-grains.