Most scholars and policy-makers conceive of legitimacy as a resource that allows political institutions and governance mechanisms to operate smoothly and effectively. However, the support in empirical research for this claim is mixed or lacking, and some studies even indicate the opposite relationship. To reconcile legitimacy theory with these findings, we argue that legitimacy under some conditions represents a cost, in the sense that important decisions become more difficult to make and to implement. Legitimacy makes agents as well as audiences of political institutions complacent with status quo, ignorant of implementation problems, and inattentive to private interests which undermine collective action. We specify the basic concepts, causal mechanisms, scope conditions, and expected effects in this theory, which is then illustrated through an in-depth case study of reform politics in the African Union (AU). This analysis shows that the quick increase in the AU’s legitimacy after its establishment in 2002 was accompanied by rhetorical and symbolic policy-making with negative rather than positive effects on substantive decision-making and policy implementation. In contrast, the significant decrease in legitimacy of the AU in recent years has been followed by a rapid increase in substantive decision-making and implementation through institutional reforms. We conclude, therefore, that scholars interested in effects of legitimacy need a theory to conceive of legitimacy as both a cost and a resource depending on contextual factors that we specify and suggest for further research.