Oxygen, one of the most abundant elements on Earth, often forms an undesired interstitial impurity or ceramic phase (such as an oxide particle) in metallic materials. Even when it adds strength, oxygen doping renders metals brittle1-3. Here we show that oxygen can take the form of ordered oxygen complexes, a state in between oxide particles and frequently occurring random interstitials. Unlike traditional interstitial strengthening4,5, such ordered interstitial complexes lead to unprecedented enhancement in both strength and ductility in compositionally complex solid solutions, the so-called high-entropy alloys (HEAs)6-10. The tensile strength is enhanced (by 48.5 ± 1.8 per cent) and ductility is substantially improved (by 95.2 ± 8.1 per cent) when doping a model TiZrHfNb HEA with 2.0 atomic per cent oxygen, thus breaking the long-standing strength-ductility trade-off11. The oxygen complexes are ordered nanoscale regions within the HEA characterized by (O, Zr, Ti)-rich atomic complexes whose formation is promoted by the existence of chemical short-range ordering among some of the substitutional matrix elements in the HEAs. Carbon has been reported to improve strength and ductility simultaneously in face-centred cubic HEAs12, by lowering the stacking fault energy and increasing the lattice friction stress. By contrast, the ordered interstitial complexes described here change the dislocation shear mode from planar slip to wavy slip, and promote double cross-slip and thus dislocation multiplication through the formation of Frank-Read sources (a mechanism explaining the generation of multiple dislocations) during deformation. This ordered interstitial complex-mediated strain-hardening mechanism should be particularly useful in Ti-, Zr- and Hf-containing alloys, in which interstitial elements are highly undesirable owing to their embrittlement effects, and in alloys where tuning the stacking fault energy and exploiting athermal transformations13 do not lead to property enhancement. These results provide insight into the role of interstitial solid solutions and associated ordering strengthening mechanisms in metallic materials.