Characterizing and understanding the mechanical properties and deformation behavior are essential for optimizing the design and operating performance of advanced materials. Importantly, slight additions of impurities can result in significant change of macroscopic mechanical properties and deformation behavior. In titanium, which is a desirable structural material for a wide range of applications due to its high strength to weight ratio and corrosion resistance, small additions of oxygen result in a dramatic increase of its overall strength and a corresponding change in the slip behavior. However the intrinsic role of oxygen has not been systematically understood due to the complication of microstructure in macro-scale materials. Through quantitative in situ transmission electron microscopy (TEM) nanomechanical testing, we show that even though Ti-O precipitation does lead to Orowan strengthening, oxygen solid solution strengthening is the dominant strengthening mechanism in binary alpha-Ti-O alloys, which significantly multiplies strength. Dislocation core structures of high purity Ti samples with systematically varied oxygen concentrations were studied by aberration-corrected high-resolution (scanning) STEM imaging. Interestingly, oxygen atoms tend to segregate at dislocation cores with increasing oxygen concentration, thereby stabilizing the screw dislocations and maintaining the straightness of the dislocation lines. In contrast, screw dislocations tend to be bent with some edge component in materials with less oxygen, resulting in higher dislocation mobility. Theoretical simulations were also performed to study the influence of oxygen on the three-dimensional dislocation core structure at the atomic scale, where the results are well in agreement with the two-dimensional experimental observations.