Perhaps the most fundamental question in contemporary European Union politics is whether the existing division and sharing of competences between national and supranational levels is pragmatically and normatively justifiable. In his classic book, Governing in Europe (1999), Fritz Scharpf argues that the current policy mix is sub-optimal and, therefore, democratically illegitimate, because the multi-level European polity lacks the ‘problem-solving capacity’ necessary to permit citizens and their representatives to bargain to optimal outcomes. Instead it is likely to trigger a vicious circle of downward adaptations in social policy and public services that are likely to sap the EU's support. Scharpf recommends granting domestic social welfare policies constitutional status in EU jurisprudence, and permitting ‘differentiated integration’ or ‘flexibility’ for high-standard countries to legislate as an EU sub-group. In this challenge by Scharpf to the ‘output legitimacy’ of the EU, we argue, a number of important issues remain unresolved. First, his argument rests on an implicit and insufficiently elaborated conception of the public interest in maintaining or expanding current patterns of social welfare protection. Second, any effort to specify this “public interest” must address three fundamental problems of democratic theory, namely the status of uninformed or inexpert citizens, underlying biases in democratic representation, and proper scope of majoritarian decision-making. Third, and fully in the spirit of the concerns raised in Governing in Europe, we suggest two possible strategies for addressing these concerns and some tools for rethinking output legitimacy and its relation both to the ‘public interest’ and to participatory procedures. The research agenda on democratic legitimacy in Europe launched by Scharpf is likely to be a lively one for some time to come.