The conceptual framework for nature-based solutions (NbS) is well developed, however realizing the potential of NbS at scale and in widespread professional practice in infrastructure systems depends on overcoming operational challenges rooted in the historical policies and engineering practices of the action agencies capable of implementation. In this article, we explore levee setbacks as a NbS for improving the sustainability of leveed river corridors within the context of the United States (US) and its primary action agency of flood risk management, the Army Corps of Engineers (USACE). By identifying the social and environmental consequences of historical levee management and linking these consequences with historical policies and engineering practices, we highlight knowledge gaps, challenges and opportunities for progress with NbS. We also briefly discuss USACE’s decision-making processes for infrastructure investments and the valuation of ecosystem services as it pertains to operationalizing setbacks in practice. We then develop a case study of a recent setback on the Missouri River to showcase how USACE overcame implementation challenges. Lessons from past levee corridor management in the US, and USACE’s current corrective actions, may help foster understanding of how to overcome operational challenges in the implementation of setbacks in other social and political contexts.