Beads and other ‘body ornaments’ are very widespread components of the archaeological record of early modern humans (Homo sapiens). They appear first in the Middle Stone Age in Africa, and somewhat later in the Early Upper Paleolithic of Eurasia. The manufacture and use of ornaments is widely considered to be evidence for significant developments in human cognition. In our view, the appearance of these objects represents the interaction of evolved cognitive capacities with changing social and demographic conditions. Body ornamentation is a medium or technology for communication, particularly of socially-relevant information. The widespread adoption of beads and other discrete objects as media for communication implies changes in the complexity and stability of social messages, as well as the scale of social networks. The relatively sudden appearance of beads in the Paleolithic archaeological record coincides with genetic and archaeological evidence for expansion of human populations. We argue that these changes reflect expanding scales of social interaction and more complex social landscapes resulting from unprecedentedly large and internally differentiated human populations.