In the field of global education policy, it is common for scholars to reflect on the progress made toward internationally agreed-upon agendas, such as Education for All (EFA). However, scant research has turned the gaze back on the major multilateral institutions that commit to taking the lead in meeting these agendas in order to ask, what implications do such agendas have for these organizations? We respond in this article by investigating the way in which UNESCO used its position as the coordinator of EFA to help it regain some of the legitimacy it lost in the preceding decades. To do so, the article first elaborates a tripartite conceptualization of organizational legitimacy and then applies it to the two prongs of UNESCO's strategy--EFA coordination and the production of the Global Monitoring Reports (GMRs) during a key period, 2000-2014, that were at the forefront of UNESCO's efforts to rebrand and reposition itself in the context of multilateralism.