One of the greatest unsolved puzzles in the study of cultural evolution is the first emergence of large-scale, complex civilizations. Social scientists and historians have long puzzled over the dynamics of large hierarchical societies and the mechanisms responsible for their survival and spread. But less is known about the origins of complex societies, which first emerged in only a few places around the world, leaving behind no written records of the process by which this quantum leap in human social organization occurred. The excavations at Çatalhöyük may help solve the puzzle. We argue that a major factor driving the emergence of complex society was religious routinization. The frequency of rituals appears to have increased over the course of settlement at Çatalhöyük and this may have had major consequences for the scale and structure of Neolithic society. This argument permits a conciliatory stance on the relationship between religion’s “vitality,” as conceptualized in much of this volume, and its “functionality” in bolstering a social order. In fact these two aspects of religion are intimately interconnected - stripped of its vitality religion’s social functions could hardly be fulfilled. The evidence from Çatalhöyük suggests that the earliest functions of religion were not to legitimate political and economic inequalities. Initially religion’s function was to bind together small tribal groups, but gradually, as agriculture intensified, this ancient function faded and religion became a means of reproducing much larger (if more diffuse) group identities. This entailed a change also in religion’s vitality - a shift from esoteric mystery cult to something more ideologically uniform, in some ways less awe-inspiring and more controlling. The exploitation of this new kind of religion by elites occurred much later, however, entailing the evolution of new forms of religious vitality.