The ability to adapt to social and environmental change is an increasingly critical feature of environmental governance. However, an understanding of how specific features of governance systems influence how they respond to change is still limited. Here we focus on how system features like diversity, heterogeneity, and connectedness impact stability, which indicates a system's capacity to recover from perturbations. Through a framework that combines agent-based modeling with "generalized"dynamical systems modeling, we model the stability of thousands of governance structures consisting of groups of resource users and non-government organizations interacting strategically with the decision centers that mediate their access to a shared resource. Stabilizing factors include greater effort dedicated to venue shopping and a greater fraction of non-government organizations in the system. Destabilizing factors include greater heterogeneity among actors, a greater diversity of decision centers, and greater interdependence between actors. The results suggest that while complexity tends to be destabilizing, there are mitigating factors that may help balance adaptivity and stability in complex governance. This study demonstrates the potential in applying the insights of complex systems theory to managing complex and highly uncertain human-natural systems in the face of rapid social and environmental change.