Ti and titanium alloys are preferred for cryogenic applications, particularly at a liquid hydrogen temperature of 20 K, in aerospace due to their high specific strength, good corrosion resistance, low magnetic permeability, and low thermal expansion coefficient. Currently, the most common cryogenic titanium alloys are extra-low interstitial α-type and near α-type alloys. However, they exhibit inadequate age hardening and low cold-forming ability. Furthermore, they do not meet the enhanced strength-ductility requirements for cryogenic structural components. Metastable β-type titanium alloys with a {332}<113> twinning-induced plasticity (TWIP) effect have shown enhanced mechanical properties, such as a favorable balance of strength-ductility at ambient and cryogenic temperatures. Therefore, they are considered promising titanium alloy candidates for cryogenic applications. The content of interstitial elements, particularly the O content, has a substantial impact on the cryogenic ductility of titanium alloys. Therefore, all cryogenic titanium alloys have extremely rigorous requirements regarding the O content. However, the effect of O content on the cryogenic tensile behavior of {332}<113> TWIP alloys remains unclear. This study investigated the cryogenic tensile behavior of Ti-15Mo alloy with O contents of 0.2% and 0.4% (mass fraction, the same below) at 20 K. The tests were conducted using HRTEM, FIB, EBSD, SEM, OM, and a tensile testing machine fitted with a cryogenic system. Results show that the alloy comprising 0.2%O content (0.2O alloy) exhibits a good combination of tensile strength (1825 MPa) and elongation (7.5%). This alloy displays typical microvoid coalescence fracture characteristics. Alternatively, the alloy with 0.4%O content (0.4O alloy) presents a high tensile strength of 1973 MPa, a relatively low elongation of 1.5%, and typical cleavage fracture characteristics. The discrepancy in cryogenic tensile properties between the two alloys can be attributed to the effect of O content on the formation of {332}<113> twins. Several {332}<113> twins appear in the 0.2O alloy, whereas only a small number of twins are observed near the fracture region in the 0.4O alloy. The exceptional strength of the 0.2O alloy is attributed to the enhanced critically resolved shear stress of twinning, while the impressive elongation is attributed to the formation of numerous twins that impede local plastic deformation. The 0.2O alloy exhibits a noticeably serrated tensile curve and multiple necking. The activation of twins in the necking region hinders local plastic deformation and necking, thus enhancing the strength-ductility combination. Hence, by effectively using the interstitial element O, the cryogenic mechanical properties of metastable β-type titanium alloys can be effectively tailored as per requirements.