This article combines Aoki’s institutional complementarity concept with actor-centered institutional analysis of action situations to study herder behavior and institutional change in a complex pastoral social–ecological system. Transformation of the Mongolian Steppe Ecosystem in the face of climate and social change has led to a decline in pastoral mobility, which in turn is making the ecosystem less sustainable. Responding to this concern, Mongolian policymakers have designed pasture use and conservation policies. We evaluate whether the enacted policies are complementary to herders’ strategic choices. First, we reconstruct institutional choices herders make in the commons domain, where herders interact to use common pastures. Second, we track this process in the political economy domain, where pasture users support or resist government policies. Finally, we evaluate the complementarity of the strategic choices and resulting institutions in the interdependent action situations of both domains. In combination with game-theoretic model building, we have employed the process tracing method during field research in Mongolia. We have not identified any evident, stable institutional complementarity between high pastoral mobility and support for a policy of leasing and certification of land for winter and spring camps. Conversely, our findings do suggest that policies for establishing pasture user groups and pasture use planning can be effective. A critical mass of herders choosing to comply with these policies and engage in pastoral mobility will be crucial for sustaining the ecosystem. This will strengthen conditions for institutional complementarity and create a new institutional arrangement overall.