Background: Medication-overuse headache leads to high disability and decreased quality of life, and the best approach for withdrawal has been debated. Aim: To compare change in disability and quality of life between two withdrawal programs. Methods: We randomized medication-overuse headache patients to program A (two months without acute analgesics or migraine medications) or program B (two months with acute medications restricted to two days/week) in a prospective, outpatient study. At 6 and 12 months, we measured disability and headache burden by the Headache Under-Response to Treatment index (HURT). We estimated quality of life by EUROHIS-QOL 8-item at 2-, 6-, and 12-month follow-up. Primary endpoint was disability change at 12 months. Results: We included 72 medication-overuse headache patients with primary migraine and/or tension-type headache. Fifty nine completed withdrawal and 54 completed 12-month follow-up. At 12-month follow-up, 41 patients completed HURT and 38 completed EUROHIS-QOL 8-item. Disability reduction was 25% in program-A and 7% in program-B (p = 0.027). Headache-burden reduction was 33% in program-A and 3% in program-B (p = 0.005). Quality of life was increased by 8% in both programs without significant difference between the programs (p = 0.30). At 2-month follow-up, quality of life increased significantly more in program-A than program-B (p = 0.006). Conclusion: Both withdrawal programs reduced disability and increased quality of life. Withdrawal without acute medication was the most effective in reducing disability in medication-overuse headache patients. Trial registration: Clinicaltrials.gov (NCT02903329).