Introduction The objective of this review is to provide an evidence-based discussion of different treatment strategies for medication-overuse headache (MOH). Method We searched PubMed for articles discussing the treatment and prognosis of MOH published between 2004 and August 2014. Titles, abstract and articles were reviewed systematically. The level of evidence provided by each study of the included articles was determined according to the American Academy of Neurology Clinical practice guideline manual. We discuss the level of evidence to support the early discontinuation/withdrawal of overused medications, the level of evidence to support the use of preventive treatment, the short- and long-term prognosis, and the outcome according to the class of drug overused in patients diagnosed with MOH. Results The initial search resulted in 1313 articles; 68 articles met our inclusion criteria and were discussed. The level of evidence to support early discontinuation of overused medications alone is low due to the absence of controlled studies. Adding preventive medication to early discontinuation led to a better outcome than early discontinuation alone. For patients with chronic migraine (CM) and medication overuse (MO), there are large randomized control trials supporting the use of onabotulinumtoxinA and topiramate without early discontinuation of overuse; however, the evidence is limited since data were obtained from post hoc analysis. Conclusion Considering current available evidence and the systemic toxicity of overusing acute headache medication, we suggest discontinuation of the overused medication with the addition of preventive medication. Appropriately sized, randomized controlled trials evaluating the safety and long-term efficacy of preventive medication plus early discontinuation of overuse vs preventive medication alone vs early discontinuation of overuse alone are needed.