How are constitutional rules sustained? The general problem concerns how to structure the political game so that all the players – elected officials, the military, economic actors, and citizens – have incentives to respect the rules. In this paper, we investigate this problem in the context of how the institutions of federalism are sustained. A central design problem of federalism is how to create institutions that at once grant the central government enough authority to provide central goods and police the sub–units, but not so much that it usurps all of public authority. Using a game theoretic model of institutional choice, we show that, to survive, federal structures must be self–enforcing: the center and the states must have incentives to fulfill their obligations within the limits of federal bargains. Our model investigates the tradeoffs among the benefits from central goods provision, the ability of the center to impose penalties for non–compliance, and the costs of states to exit. We also show that federal constitutions can act as coordinating devices or focal solutions that allow the units to coordinate on trigger strategies in order to police the center. We apply our approach to a range of federations, including the United States under the Articles and the Constitution, modern China, and Russia.