Several studies have shown the benefit of withdrawal therapy when medication overuse headache (MOH) is suspected. Our aim was to compare the effect of withdrawal therapy in patients followed by a neurologist (group A, n = 42) and a primary care physician (PCP) (group B, n = 38). Patients were randomized to A or B, and follow-up was at 3, 6 and 12 months. Calculated mean headache (MH at 6 months + MH at 12 months)/2 (primary end-point) was similar; A 1.04 (0.87, 1.21) and B 1.02 (0.82, 1.21) (P = 0.87). The number of patients with 50% improvement of headache days was also similar; 14/42 in group A vs. 12/34 in B (P = 0.86) at 3 months, 15/42 vs. 11/33 (P = 0.83) at 6 months and 15/42 vs. 14/38 (P = 0.92) at 12 months. Days without headache during the last 9 months of follow-up were 123 (96, 150) in group A and 137 (112, 161) in B (P = 0.62). After 3 months one-third were classified as MOH. Patients with MOH improved similarly in group A and B, and so did patients without MOH. Within 1 year 7/42 in A and 9/38 in B had recurrent medication overuse (P = 0.43). In summary, there were no significant differences in follow-up results between the two groups.