We develop a cultural evolutionary theory of the origins of prosocial religions and apply it to resolve two puzzles in human psychology and cultural history: (1) the rise of large-scale cooperation among strangers and, simultaneously, (2) the spread of prosocial religions in the last 10–12 millennia. We argue that these two developments were importantly linked and mutually energizing. We explain how a package of culturally evolved religious beliefs and practices characterized by increasingly potent, moralizing, supernatural agents, credible displays of faith, and other psychologically active elements conducive to social solidarity promoted high fertility rates and large-scale cooperation with co-religionists, often contributing to success in intergroup competition and conflict. In turn, prosocial religious beliefs and practices spread and aggregated as these successful groups expanded, or were copied by less successful groups. This synthesis is grounded in the idea that although religious beliefs and practices originally arose as nonadaptive by-products of innate cognitive functions, particular cultural variants were then selected for their prosocial effects in a long-term, cultural evolutionary process. This framework (1) reconciles key aspects of the adaptationist and by-product approaches to the origins of religion, (2) explains a variety of empirical observations that have not received adequate attention, and (3) generates novel predictions. Converging lines of evidence drawn from diverse disciplines provide empirical support while at the same time encouraging new research directions and opening up new questions for exploration and debate.