Over the last two decades intergovernmental organizations have supported the initiation of National Forest Programs (NFPs): forums for joint deliberation by the state, private companies and NGOs that are intended to resolve conflicts over forestry and enhance sustainability. However, NFPs do not always reconcile conflicting perspectives or produce legitimate strategies for sustainable forestry. Thus, further analysis of NFPs' organization and processes is required, including exploration of effective means to address such challenges in early stages. These are key concerns of this paper, focusing on the first process to establish a Swedish NFP. Possibilities for an NFP to constitute a new arena for deliberation and consensus-building, producing forest policy statements and action plans considered legitimate by various stakeholders, are discussed. A number of key challenges are identified through a theoretical framework based on notions regarding the input and output legitimacy of collaborative governance. Analysis of official documentation, records of public hearings and stakeholder comments from the establishment phase in 2013–2015 suggests that the process will continually face a number of challenges, including balancing production and conservation values in the new bio-economy and securing equal stakeholder participation. The paper concludes with some remarks on the future of the NFP process.