<p>Early modern history abounds with descriptions of “barbarians,” a term originating in ancient Greece and later applied to people deemed uncivilized. Historical knowledge about these groups comes largely from colonial or imperialist outsiders who mischaracterized them as irrational and violent. This characterization masks the fact that these decentralized groups achieved large-scale strategic coordination in the absence of centralized power. This paper examines historical examples of such collectives, illustrating how they leveraged flexible cultural and political repertoires, including socially cooperative violence, to maintain autonomy while scaling up collective action. We present a framework for understanding these dynamics that emphasizes how groups drew upon repertoires of institutions, resources, and strategies and analyze four case studies to explore how decentralized societies coordinated effectively without central authority. Finally, we suggest ways archaeologists might identify similar patterns in the past, offering a fresh perspective on the structural dimensions of large-scale, decentralized societies.</p>