The microstructure and microhardness evolution of a Ti-15(wt.%)Mo/TiB metal-matrix composite (MMC) during high-pressure torsion (HPT) at 400 °C was studied. The composite was fabricated by spark plasma sintering of a Ti, Mo and TiB2 powders mixture at 1200 °C. In the initial condition, the structure of the composite consisted mainly of body-centered cubic (bcc) Ti solid solution and TiB whiskers. An increase in dislocation density, a considerable decrease in a grain size in the bcc Ti matrix, and breaking/rearrangement of the TiB whiskers were observed during HPT. The (sub)grain size in the bcc Ti matrix attained after 1 revolution was ~75 nm and then gradually decreased to ~55 nm after 5 revolutions. The TiB particle sizes after 5 revolutions was found to be 130–210 nm. The microhardness increased with strain from 575 HV in the initial state to 730 HV after 5 revolutions. Various hardening mechanisms’ contributions in the Ti-15Mo/TiB were evaluated.