Article ; Social-ecological systems are often highly complex, making effective governance a considerable challenge. In large, heterogeneous systems, hierarchical institutional regimes may be efficient, but effective management outcomes are dependent on stakeholder support. This support is shaped by perceptions of legitimacy, which risks being undermined where resource users are not engaged in decision-making. Although legitimacy is demonstrably critical for effective governance, less is known about the factors contributing to stakeholders’ perceptions of legitimacy or how these perceptions are socially differentiated. We quantitatively assessed stakeholder perceptions of legitimacy (indicated by support for rules) and their contributory factors among 307 commercial fishers and tourism operators in Australia’s Great Barrier Reef Marine Park. Legitimacy was most strongly associated with trust in information from governing bodies, followed by confidence in institutional performance and the equity of management outcomes. Legitimacy differed both within and among resource user groups, which emphasizes the heterogeneous nature of commonly defined stakeholder groups. Overall, tourism operators perceived higher legitimacy than did commercial fishers, which was associated with higher trust in information from management agencies. For fishers, higher levels of trust were associated with: (1) engagement in fisheries that had high subsector cohesion and positive previous experiences of interactions with governing bodies; (2) location in areas with greater proximity to sources of knowledge, resources, and decision-making; and (3) engagement in a Reef Guardian program. These findings highlight the necessity of strategies and processes to build trust among all user groups in large social-ecological systems such as the Great Barrier Reef Marine Park. Furthermore, the social differentiation of perceptions that were observed within user groups underscores the importance of targeted strategies to engage groups that may not be heard through traditional governance channels. ; The Social and Ecological Long Term Monitoring Program (SELTMP) for the Great Barrier Reef Marine Park was established in 2011 with funding provided by the Australian Government under the National Environment Research Program (NERP). We thank the SELTMP team for their support and collaboration. We also sincerely thank the commercial fishers and tourism operators that were part of this research and the interviewers that were involved. The arguments presented here are the sole responsibility of the authors. This paper was developed in a workshop funded by the Julius Career Award, the Commonwealth Scientific and Industrial Research Organisation (CSIRO), and the Environment and Sustainability theme of the University of Exeter’s Humanities and Social Science Strategy. The authors acknowledge additional support from the University of Exeter’s Outward Mobility Fund (R. T.), the Australian Research Council (T. M., A. A., B. J. B.), CSIRO (J. A.), and AusAID (A. A.).