Interstitial oxygen embrittles titanium, particularly at cryogenic temperatures, which necessitates a stringent control of oxygen content in fabricating titanium and its alloys. Here, we propose a structural strategy, via grain refinement, to alleviate this problem. Compared to a coarse-grained counterpart that is extremely brittle at 77 K, the uniform elongation of an ultrafine-grained (UFG) microstructure (grain size ~ 2.0 µm) in Ti-0.3wt.%O is successfully increased by an order of magnitude, maintaining an ultrahigh yield strength inherent to the UFG microstructure. This unique strength-ductility synergy in UFG Ti-0.3wt.%O is achieved via the combined effects of diluted grain boundary segregation of oxygen that helps to improve the grain boundary cohesive energy and enhanced dislocation activities that contribute to the excellent strain hardening ability. The present strategy will not only boost the potential applications of high strength Ti-O alloys at low temperatures, but can also be applied to other alloy systems, where interstitial solution hardening results into an undesirable loss of ductility.