The microstructure and properties of titanium-based alloys can be tailored using severe plastic deformation. The structure and microhardness of Ti–4 wt.% Co alloy have been studied after preliminary annealing and following high pressure torsion (HPT). The Ti–4 wt.% Co alloy has been annealed at 400, 500, and 600 °C, i.e., below the temperature of eutectoid transformation in the Ti–4 wt.% Co system. The amount of Co dissolved in α-Ti increased with increasing annealing temperature. HPT led to the transformation of α-Ti in ω-Ti. After HPT, the amount of ω-phase in the sample annealed at 400 °C was about 8085%, i.e., higher than in pure titanium (about 40%). However, with increasing temperature of pre-annealing, the portion of ω-phase decreased (60–65% at 500 °C and about 5% at 600 °C). The microhardness of all investigated samples increased with increasing temperature of pre-annealing.