The emergence of megacities raises a number of conceptual questions for political science and public administration. It is as yet unclear to what extent the huge size of megacities presents conditions that require qualifications or adaptations to existing concepts and theoretical models for the analysis of governance in megacities as compared to urban regions of lesser size. The aim of this paper is to discuss this conceptual issue. With respect to policy problems, distinctions between megacities and smaller cities seem to be a matter of degree rather than quality. With respect to governability, however, megacities seem to present particular problems: institutional complexity, a weakness of public resources and, linked to this, an actor system where private businesses and the informal sector plays a more important role, as well as a strong entwinement between local and national governments. Only the new regionalist approach rests on theoretical premises that can, realistically, seen to be met in megacities. Analysing megacity governance on the basis of the new regionalist approach means to focus our attention on four elements that facilitate coordination by negotiation: (a) actors’ attitudes towards sustained negotiation as the core means of policy-coordination, (b) the emergence of consensus as a mode of interaction, (c) the construction of political leadership at the scale of the megacity, (d) the use of slack in the multi-levelled relationships by policy-relevant actors.