Beta-Ti alloys have been intensively investigated in the last years because of their favorable low Young's moduli, biocompatibility and bio-inertness, making these alloys interesting candidates for implant materials. Due to their low mechanical strength, efforts are currently devoted to increasing it. A promising way to improve the strength is to tailor the microstructure using severe plastic deformation (SPD). In this investigation high pressure torsion was used to refine the microstructure of a Ti-45wt.%Nb alloy inducing a grain size of ~50 nm. The main focus of the subsequent investigations was devoted to the thermal stability of the microstructure. Isochronal heat-treatments performed for 30 min in a temperature range up to 500 °C caused an increase of hardness with a peak value at 300 °C before the hardness decreased at higher temperatures. Simultaneously, a distinct temperature-dependent variation of the Young's modulus was also measured. Tensile tests revealed an increase in strength after annealing compared to the SPD-state. Microstructural investigations showed that annealing causes the formation of α-Ti. The findings suggest that the combination of severe plastic deformation with subsequent heat treatment provides a feasible way to improve the mechanical properties of SPD-deformed β-Ti alloys making them suitable for higher strength applications.