Today, the world faces grand challenges that are both daunting and urgent to address. The decarbonization challenge in particular requires states to mobilize a range of actors to achieve structural changes. In this context, there has been a proliferation of orchestration attempts by states, whereby they use soft or indirect forms of steering to coordinate and engage intermediaries to achieve policy objectives. This type of steering raises a number of questions: How can such forms of steering gain legitimacy among the targeted actors and how can this legitimacy be maintained in the face of competing interests? This paper uses the case of the Fossil Free Sweden Initiative to highlight key factors and considerations in establishing and maintaining legitimacy in the orchestration of a varied set of non-state actors with differing interests. Specifically, the paper makes two core contributions to existing literature. Theoretically, it highlights how institutional legitimacy is obtained through a balancing act of stakeholder demands at different levels. Empirically, it examines how Sweden, considered a climate leader, governs toward decarbonization through national orchestration as an important tool. The paper thereby offers new insights into the legitimacy of orchestration with significant implications for how to understand rule-making and governance with the use of intermediaries. It particularly highlights how power and agency can create a governance dilemma for the orchestrator that may undermine legitimacy in the long term.