Human societies are examined as distinct and coherent groups. This trait is most parsimoniously considered a deeply rooted part of our ancestry rather than a recent cultural invention. Our species is the only vertebrate with society memberships of significantly more than 200. We accomplish this by using society-specific labels to identify members, in what I call an anonymous society. I propose that the human brain has evolved to permit not only the close relationships described by the social brain hypothesis, but (...) also, at little mental cost, the anonymous societies within which such alliances are built. The human compulsion to discover or invent labels to “mark” group memberships may originally have been expressed in hominins as vocally learned greetings only slightly different in function from chimpanzee pant hoots (now known to be society-specific). The weight of evidence suggests that at some point, conceivably early in the hominin line, the distinct groups composed of several bands that were typical of our ancestors came to be distinguished by their members on the basis of multiple labels that were socially acquired in this way, the earliest of which would leave no trace in the archaeological record. Often overlooked as research subjects, these sizable fission-fusion communities, in recent egalitarian hunter-gatherers sometimes 2,000 strong, should consistently be accorded the status of societies, in the same sense that this word is used to describe tribes, chiefdoms, and other cultures arising later in our history. The capacity of hunter-gatherer societies to grow sufficiently populous that not all members necessarily recognize one another would make the transition to larger agricultural societies straightforward. Humans differ from chimpanzees in that societal labels are essential to the maintenance of societies and the processes giving birth to new ones. I propose that anonymous societies of all kinds can expand only so far as their labels can remain sufficiently stable. (shrink)