We present a prospective 4-year follow-up study of 96 patients with medication overuse headache following withdrawal. Complete datasets were available from 85 patients (89%) 6 months, from 79 patients (82%) 1 year and from 75 patients (78%) 4 years after withdrawal. Twenty-six patients (31%) relapsed within the first 6 months after withdrawal. The number of relapses increased to 32 (41%) 1 year and to 34 (45%) 4 years after withdrawal. The 4-year relapse rate was lower in migraine than in tension-type headache (32% vs. 91%, P<or=0.001) and combination of migraine and tension-type headache (32% vs. 70%, P<or=0.027) and also lower in patients overusing triptans than analgesics (21% vs. 71%, P<or=0.001). The study suggests that the majority of relapses occur within the first year after withdrawal and that the long-term success of withdrawal depends on the type of primary headache and the type of overused medication.