Understanding the linkages between social and ecological systems is key to developing sustainable natural resource management (NRM) institutions. Frequently, however, insufficient attention is paid to the historical development of NRM institutions. Instead, discussion largely focuses on models of economic efficiency at the expense of the cultural, historical, and ecological contexts within which institutions develop. Here we use the research program of historical ecology to explore the development, maintenance, and change of two contemporary fire management institutions in northern Australia and Colorado, USA, to demonstrate how social institutions and ecological systems change and resist change over time and how institutions interact across scales to negotiate contrasting goals and motivations. We argue that these NRM institutions are not strictly speaking evolutionary or adaptive, and that historical context is critical when evaluating how and why particular institutions and institutional relationships develop. As with ecosystems, the present characteristics of the NRM institutions are dependent on what has happened before and their efficacy can only be evaluated retrospectively. Therefore, an understanding of history is essential to questions of the desirability and feasibility of institutional change where such shifts are required from an ecological, social, or economic perspective. We further propose that institutional conflict arises from the differing goals and motives of resource management institutions at different scales. Our cases reveal that larger-scale institutions can be successful at achieving narrowly defined goals but often fall short of achieving socially desirable sustainable outcomes. Our findings support the use of narratives of community history, place, and being in considering the resilience and sustainability of social-ecological systems. We offer that historical ecology is complementary with institutional and economic approaches to the analysis of NRM institutions, and possesses a particular strength in linking ecology to the values and norms of small social groups.