Multilevel selection is a powerful theoretical framework for understanding how complex hierarchical systems evolve by iteratively adding control levels. Here I apply this framework to a major transition in human social evolution, from small-scale egalitarian groups to large-scale hierarchical societies such as states and empires. A major mathematical result in multilevel selection, the Price equation, specifies the conditions concerning the structure of cultural variation and selective pressures that promote evolution of larger-scale societies. Specifically, large states should arise in regions where culturally very different people are in contact, and where interpolity competition – warfare – is particularly intense. For the period of human history from the Axial Age to the Age of Discovery (c.500 BCE–1500 CE), conditions particularly favorable for the rise of large empires obtained on steppe frontiers, contact regions between nomadic pastoralists and settled agriculturalists. An empirical investigation of warfare lethality, focusing on the fates of populations of conquered cities, indicates that genocide was an order of magnitude more frequent in steppe-frontier wars than in wars between culturally similar groups. An overall empirical test of the theory’s predictions shows that over ninety percent of largest historical empires arose in world regions classified as steppe frontiers.