Obesity remains a major public health challenge across OECD countries and policy-makers globally require successful policy precedents. This paper analyzes New York City’s innovative experiences in regulatory approaches to nutrition. We combined a systematic documentary review and key informant interviews (n = 9) with individuals directly involved in nutrition policy development and decision-making. Thematic analysis was guided by Kingdon’s three-streams-model and the International Obesity Task Force’s evidence-based decision-making framework. Our findings indicate that decisive mayoral leadership spearheaded initial agenda-change and built executive capacity to support evidence-driven policy. Policy-makers in the executive branch recognized the dearth of evidence for concrete policy interventions, and made contributing to the evidence base an explicit goal. Their approach preferred decision-making through executive action and rules passed by the Board of Health that successfully banned trans-fats from food outlets, set institutional food standards, introduced menu labeling requirements for chain restaurants, and improved access to healthy foods for disadvantaged populations. Although the Health Department collaborated with the legislature on legal and programmatic food access measures, there was limited engagement with elected representatives and the community on regulatory obesity prevention. Our analysis suggests that this hurt the administration’s ability to successfully communicate the public health messages motivating these contentious proposals; contributing to unexpected opposition from food access and minority advocates, and fueling charges of executive overreach. Overall, NYC presents a case of expert-driven policy change, underpinned by evidence-based environmental approaches. The city’s experience demonstrates that there is scope to redefine municipal responsibilities for public health and that incremental change and contentious public discussion can impact social norms around nutrition.