<p>Current guidelines recommend behavioral treatment (BT) as the first intervention for patients with obesity. However, a substantial minority (35–50%) do not achieve a clinically meaningful loss of ≥5%. Anti-obesity medications (AOMs) are recommended when target weight loss is not achieved; however, their efficacy among BT nonresponders has not been established. This double-blind, randomized controlled proof-of-principle study evaluated whether augmenting BT with AOM improved 24-week weight loss compared to BT with placebo in early nonresponders to BT. A total of 147 adults with a body mass index ≥31 kg m⁻² (≥28 kg m⁻² with obesity-related comorbidity) completed an initial 4-week BT run-in. The 76 early nonresponders who lost &lt;2.0% of initial weight were then randomized to 24 weeks of either BT plus placebo (BT + P, <i>n</i> = 38) or BT plus AOM (phentermine = 15.0 mg d⁻¹, <i>n</i> = 38). Early responders received ongoing BT and were not part of the randomized trial. The primary outcome was met; early nonresponders assigned to BT + AOM had a greater mean (±s.e.) reduction in weight of 5.9 ± 0.7% from randomization to week 24, as compared to 2.8 ± 0.7% for those assigned to BT + P (mean difference = 3.1 ± 1.0, 95% confidence interval = 1.1–5.1%, Cohen’s <i>d</i> = 0.73, <i>P</i> = 0.003). Stepping up early BT nonresponders to BT + AOM improves their 24-week weight loss. ClinicalTrials.gov registration: <a href="https://clinicaltrials.gov/study/NCT03779048">NCT03779048</a>.</p>