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 <c + a> 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.