Oxygen, one of the most abundant elements on Earth, often formsan undesired interstitial impurity or ceramic phase (such as an oxideparticle) in metallic materials. Even when it adds strength, oxygendoping renders metals brittle1–3. Here we show that oxygen can takethe form of ordered oxygen complexes, a state in between oxideparticles and frequently occurring random interstitials. Unliketraditional interstitial strengthening4,5, such ordered interstitialcomplexes lead to unprecedented enhancement in both strength andductility in compositionally complex solid solutions, the so-calledhigh-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 HEAwith 2.0 atomic per cent oxygen, thus breaking the long-standingstrength–ductility trade-off11. The oxygen complexes are orderednanoscale regions within the HEA characterized by (O, Zr, Ti)-richatomic complexes whose formation is promoted by the existence ofchemical short-range ordering among some of the substitutionalmatrix elements in the HEAs. Carbon has been reported to improvestrength and ductility simultaneously in face-centred cubic HEAs12,by lowering the stacking fault energy and increasing the latticefriction stress. By contrast, the ordered interstitial complexesdescribed here change the dislocation shear mode from planar slipto wavy slip, and promote double cross-slip and thus dislocationmultiplication through the formation of Frank–Read sources (amechanism explaining the generation of multiple dislocations)during deformation. This ordered interstitial complex-mediatedstrain-hardening mechanism should be particularly useful inTi-, Zr- and Hf-containing alloys, in which interstitial elementsare highly undesirable owing to their embrittlement effects, andin alloys where tuning the