This study investigated the outcome of a 5-day headache-specific multidisciplinary treatment program (MTP) and the adherence to treatment recommendations in 295 prospectively recruited consecutive headache patients [210 migraine, 17 tension-type headache (TTH), 68 combination headache, including 56 medication-overuse headache (MOH)]. Headache frequency decreased from 13.4 (±8.8) to 8.8 (±8.0) days per month after 12–18 months. Forty-three percent of the participants fulfilled the primary outcome (reduction of headache frequency of ≥50%), which was less likely in patients with combination of migraine and TTH compared to migraine (OR = 3.136, p = 0.002) or TTH (OR = 1.029, n.s.). Increasing number of headache days per month (OR = 1.092, p ≤ 0.0001) and adherence to lifestyle modifications (OR = 1.269, p = 0.004) predicted primary outcome. 51 of 56 MOH patients were treated successfully. Thirty-five percent of the patients were adherent to pharmacological prophylaxis, 61% to relaxation therapy, and 72% to aerobic endurance sports. MTP is effective in headache treatment. Adherence to therapy was associated with better outcome.