In December 2003, Libya announced it would abandon its nuclear and chemical weapons programs and admit inspectors from the International Atomic Energy Agency and the Organisation for the Prohibition of Chemical Weapons. Further, it would also eliminate missiles with ranges over 300 km in accordance with Missile Technology Control Regime limits. Following decades of sponsoring terrorism abroad and serving as the original “rogue state,” Libya’s decision to join international governance regimes aimed at constraining weapons of mass destruction was a significant shift. This chapter theorizes “nuclear deals” as settlements that resolve nuclear weapons proliferation disputes by linking nuclear concessions to non-nuclear issues, situating them in the evolving multilateral nonproliferation regime. Using Libya’s 2003 decision to dismantle its WMD and long-range missile programs, it reconstructs the secret intelligence-led US-UK-Libyan talks to illustrate how the nonproliferation regime’s founding, deepening, and broadening created the institutional opportunities and constraints that structured bargaining.