A Ti5Ta1.8Nb alloy with the major phase as alpha (hcp) Ti has been subjected to severe plastic deformation by means of cryo-rolling. Significant grain refinement (from similar to 5 mu m to similar to 60 nm) has been observed. The mechanism of grain refinement was studied by analysis of lattice strain variations with increase in cold work using XRD technique. Various intermediate stages, such as hardening, alignment of dislocations, cell formation and criticality before new grain formation, were identified. Formation of cells with dislocations alignment at the boundaries and then finally forming an ultra-fine grain structure was confirmed by transmission electron microscopy studies. Detailed grain boundary characterisation has been carried out using high-resolution transmission electron microscopy studies and crystallographic texture analysis. The grain-refined structure was found to possess a large fraction of high angle boundaries identified also as special boundaries by evaluating the misorientation angle/axis sets for a pair of adjacent grain boundaries.