An α-β alloy (β~8% in the stress relieved condition) of Ti-5Ta-1.8Nb has been subjected to severe plastic deformation (SPD) by cryo-rolling. The grain size of α-Ti could be reduced significantly from ~ 8µm to 100 nm and less by cryo-rolling. Extensive plastic deformation leads to grain fragmentation through the formation of defect clusters. The fragmented grains exhibit deformation texture. High resolution transmission electron microscopy (HRTEM) confirmed the presence of low and high angle grain boundaries. The role of substitutional atoms (Ta, Nb) in producing lattice strains and altering the projected potential from the atomic columns has been discussed. Although, the minor phase, β (bcc-Ti) is evident in the starting alloy, it was not observed after SPD, possibly due to extended solid solution formation (Gibbs–Thomson effect) in the fine grains or due to the stress induced transformation of the α-Ti phase.