Mediation is becoming more and more prominent as a mode of legal dispute resolution. The problem of legitimacy in mediation raises the question of why mediation is legitimate as a means of settling social disputes. This issue mirrors a long-running and deep-seated problem of legitimacy in law generally. We argue that the most promising strategy for justifying the normative force of law - namely, that law provides a mutually beneficial mechanism of social coordination - does not translate straightforwardly to the mediation context. A distinctive response to the problem of legitimacy in mediation is therefore needed. The consensual nature of mediation may render it legitimate in some contexts, but it is unlikely to do so in others. Our conclusion is threefold: the problem of legitimacy in mediation exists; it is distinct from the problem of legitimacy in law generally; and the problem is more intractable than is generally thought.