Individually, increasing the concentration of either oxygen or aluminum has a deleterious effect on the ductility of titanium alloys. For example, extremely small amounts of interstitial oxygen can severely deteriorate the tensile ductility of titanium, particularly at cryogenic temperatures. Likewise, substitutional aluminum will decrease the ductility of titanium at low-oxygen concentrations. Here, we demonstrate that, counter-intuitively, significant additions of both Al and O substantially improves both strength and ductility, with a 6-fold increase in ductility for a Ti-6Al-0.3 O alloy as compared to a Ti-0.3 O alloy. The Al and O solutes act together to increase and sustain a high strain-hardening rate by modifying the planar slip that predominates into a delocalized, three-dimensional dislocation pattern. The mechanism can be attributed to decreasing stacking fault energy by Al, modification of the "shuffle" mechanism of oxygen-dislocation interaction by the repulsive Al-O interaction in Ti, and micro-segregation of Al and O by the same cause.