Anarchy and hierarchy are two central concepts of international relations theory but as conventionally defined they cannot describe political life for most of Western history. Neither concept describes the structure of medieval politics well. Rather, many different principles of differentiation existed simultaneously, both stratificatory and segmentary. The situation was closer to anarchy as understood as the absence of overarching principles of order rather than as ‘anarchy’ in the conventional sense used in international relations and absence of government. The power of the Popes over temporal rulers was considerable, but it never corresponded to the concept ‘hierarchy’ as conventionally understood either. Between c. 700 and c. 1300, Europe became more heteronymous as time went by, not less. More principles of differentiation were developed, and both Popes and kings became more powerful. The reinvention of the papacy after the ‘Investiture Controversy’ (1075–1122) created a system of law and practices in which European monarchs and realms were embedded, but it did not create an all-powerful papacy.