This multi-center study compared the therapeutic effect of a cognitive-behavioral minimal contact program (MCT) to the effect of a brochure (bibliotherapy) for the prevention of medication overuse headache (MOH) in migraine patients. Seven German headache centers recruited 182 migraine patients with high triptan or analgesic intake frequency. Patients were randomly allocated to either the MCT-group, receiving both an MCT program and an educational brochure or to the biblio-group receiving only the brochure. All participants continued usual medical treatment. Course of headaches, intake of analgesics or triptans after training, 3 months post-training as well as 1-2 years (mean 15.7 months) later and psychological variables were defined as outcome variables. A significant decline was observed in the number of headache days (11.0-8.8), migraine days (7.3-5.7) and medication intake days (7.4-6.1) from pre to post in the MCT-group (p < 0.001 each) and in the biblio-group (p < 0.001 each). The pre-to-post-improvements were maintained from pre- to short- and from pre- to long-term follow-up (p < 0.001 each) in both groups. Both groups improved significantly from pre to post in psychological variables, e.g. pain acceptance: p < 0.001; pain catastrophizing: p < 0.001; functional pain coping: p < 0.001; and pain related internal control beliefs: p < 0.01. Psychological improvements remained stable in both groups at short- and long-term follow-up. During the study, none of the patients developed an MOH. MCT- and bibliotherapy are useful in migraine patients to prevent medication overuse headache or the transition of episodic to chronic headache.