Sustainability scientists have long studied what drives effective marine management. This chapter provides an assessment of a largely understudied factor that can alleviate compliance problems in marine management: the legitimacy of marine institutions, defined as stakeholder beliefs in the appropriate use of power by these institutions. This chapter describes the legitimacy of 19 international institutions dealing with marine issues, including the Arctic Council, European Union, and United Nations Environment, in the eyes of different types of stakeholders. The chapter then discusses how challenges arising from these legitimacy patterns could be managed to effectively address compliance problems. Insights from political science help understand that legitimacy can contribute to compliance among stakeholders, but that increased legitimacy may also entail the risk of declining public scrutiny and interest group capture. Based on this assessment, the chapter outlines a research agenda on legitimacy and effectiveness for sustainability scholars.