International society, so long the resolution to problems of collective political order, now appears to be failing in its capacity to deal with transnational challenges such as climate change, global security and financial instability. Indeed, the structure of international society itself has become a significant obstacle to such pressing issues of global governance. One striking response has been the reemergence of cities as important actors on the international stage. This article will show how these two issues are intrinsically linked. Cities have taken on new governance roles in the gaps left by hamstrung nation-states, and their contribution to an emerging global governance architecture will be a significant feature of the international relations of the 21st century. But do the new governance activities of cities represent a failure on the part of states, as some scholars have argued? Or are they a part of an emerging form of global order, in which the relationship between states, cities and other actors is being recalibrated? This article argues that the remarkable renaissance of cities in recent decades has been a result of a shift in the structure of international society, and assesses the causal drivers of this shift. It goes on to draw out some of the implications of the recalibration of the relationship between the city and the state for how we understand the emerging form of global order.