Significance Hunter-gatherers like the Ju/’hoãnsi (!Kung) San use exchange networks to dampen subsistence and reproductive risks, but almost nothing is known of how, when, and why such practices emerged. Strontium isotope analysis of one preferred San exchange item, ostrich eggshell beads, from highland Lesotho shows that since the late Middle Stone Age ∼33 ka, such networks connected ecologically complementary regions over minimal distances of several hundred kilometers. Rapidly changing environmental conditions during Marine Isotope Stage 3 (∼59 to 25 ka) likely placed a premium on developing effective means of mitigating subsistence and demographic risks, with ostrich eggshell beads providing a uniform medium of personal decoration and exchange highly suitable for binding together extended open social networks.