There is growing recognition that public lands cannot be managed as islands; rather, land management must address the ecological, social, and temporal complexity that often spans jurisdictions and traditional planning horizons. Collaborative decision making and adaptive management (CAM) have been promoted as methods to reconcile competing societal demands and respond to complex ecosystem dynamics. We detail the experiences of land managers and stakeholders in using CAM at Las Cienegas National Conservation Area (LCNCA), a highly valued site under the jurisdiction of the Bureau of Land Management (BLM). The CAM process at Las Cienegas is marked by strong stakeholder engagement, with four core elements: (1) shared watershed goals with measurable resource objectives; (2) relevant and reliable scientific information; (3) mechanisms to incorporate new information into decision making; and (4) shared learning to improve both the process and management actions. The combination of stakeholder engagement and adaptive management has led to agreement on contentious issues, more innovative solutions, and more effective land management. However, the region is now experiencing rapid changes outside managers’ control, including climate change, human population growth, and reduced federal budgets, with large but unpredictable impacts on natural resources. Although the CAM experience provides a strong foundation for making the difficult and contentious management decisions that such changes are likely to require, neither collaboration nor adaptive management provides a sufficient structure for addressing the externalities that drive uncontrollable and unpredictable change. As a result, LCNCA is exploring two specific modifications to CAM that may better address emerging challenges, including: (1) creating nested resource objectives to distinguish between those objectives that may be crucial to maintaining ecological resilience from those that may hinder a flexible response to climate change, and (2) incorporating scenario planning into CAM to explore how climate change may interact with other drivers and alter options for the future, to identify robust management actions, and to prioritize ecological monitoring efforts. The experiences at LCNCA demonstrate how collaboration and adaptive management can be used to improve social and environmental outcomes and, with modifications, may help address the full range of complexity and change that threatens to overwhelm even the best efforts to sustain public lands.