In recent years there has been a proliferation of international institutions that address climate change and energy governance, not least in the field of renewable energy. Given scarce resources, policy-makers need to prioritize which institutions to engage with. Central to this choice are considerations of the institutions’ legitimacy. The aim of this chapter is to understand how the legitimacy of international institutions is perceived under conditions of institutional complexity–ie in a context, where multiple actors work on the same issue area without overarching coordination. A questionnaire-based study examines common understandings of what makes an institution legitimate and how these understandings diverge amongst policy-makers and key stakeholder groups from different countries. Theoretically, the chapter unpacks the meaning of legitimacy under institutional complexity. Empirically, based on mixed methods, the chapter offers an assessment of legitimacy of a set of climate and energy governance institutions with different but overlapping mandates (the Clean Energy Ministerial, International Energy Agency, International Renewable Energy Agency, Renewable Energy Policy Network for the 21st Century, and United Nations Framework Convention on Climate Change). This chapter thus provides societally-relevant insights to the literature on legitimacy, with implications for how to strengthen climate and energy governance.