Different societies of states develop different fundamental institutions to govern relations between their constituent units. Whereas the governance of modern international society rests on the institutions of contractual international law and multilateralism, no such institutions evolved in Ancient Greece. Instead, the city-states developed a sophisticated, and successful, system of arbitration to facilitate ordered interstate relations. Because existing neorealist, neoliberal, and constructivist accounts of international institutions struggle to explain such variation, I develop a new constructivist account of fundamental institutional development. Societies of states are shaped by constitutional structures, which are coherent ensembles of three constitutive values: a shared belief about the moral purpose of the state, an organizing principle of sovereignty, and a norm of pure procedural justice. These deep normative structures constitute and constrain institutional design and action. Because international societies emerge in different cultural and historical contexts, they evolve different constitutional structures, leading states to construct different fundamental institutions. I illustrate this theory through a comparison of ancient Creek and modem constitutional structures and basic institutional practices.