Background There is lack of evidence on how to detoxify medication-overuse headache. Aim To compare the effect of complete stop of acute medication with restricted intake. Methods Medication-overuse headache patients were included in a prospective, outpatient study and randomized to two months' detoxification with either a) no analgesics or acute migraine-medication (program A), or b) acute medication restricted to two days/week (program B). Detoxification was followed by preventives if indicated. Patients were followed up at 2, 6 and 12 months. Percentage reduction in headache days/month after 6 months was the primary outcome. Results We included 72 medication-overuse headache patients with a primary migraine and/or tension-type headache diagnosis. Fifty-nine completed detoxification, 58 (81%) were followed up at month 6 and 53 (74%) at month 12. At month 6, program A reduced headache days/month by 46% (95% CI 34-58) compared with 22% (95% CI 11-34) in program-B ( p = 0.005), and 70% in program A versus 42% in program B were reverted to episodic headache ( p = 0.04). Migraine-days/month were reduced by 7.2 in program A ( p < 0.001) and 3.6 in program B ( p = 0.002) after 6 months. Conclusion Both detoxification programs were very effective. Detoxification without analgesics or acute migraine-medication was the most effective program. Trial registration Clinicaltrials.gov (NCT02903329).