Objective: We investigated whether telephone follow-up consultations could lead to appropriate adjustment of treatments and a higher degree of patient satisfaction among patients with migraine and tension-type headache (TTH). Background: Migraine and TTH are disabling headache forms requiring optimized treatment. Methods: In a prospective, non-randomized, quality control study with controls comparing telephone-interview intervention (TeII) with business-as-usual (BAU) treatment, we included newly referred patients with migraine and/or TTH. The TeII group was contacted by telephone by healthcare professionals at 8 and 16 weeks after the first visit addressing headache treatment. Electronic questionnaires were sent to all participants before the first visit and after 6 months. Predefined outcomes were number of patients with change in preventive and acute medication; change in headache frequency; migraine frequency; scores from the eight-item Headache Under-Response to Treatment (HURT-8) questionnaire, Insomnia Severity Index (ISI), and Hospital Anxiety and Depression Scale (HADS); and patient satisfaction after 6 months. Results: From May 2020 to April 2021, there were 230 patients enrolled in the TeII program, whereof 96 patients were included in the analysis. For the BAU group, 91 patients with similar sex and age distribution were identified via medical-record reviews in the same period. More patients in the TeII group than in the BAU group had a change in acute medication (27/96 [28%] vs. five of 91 [6%], p < 0.001) and preventive medication (28/96 [29%] vs. 12/91 [13%], p = 0.006). Headache days per month decreased in the TeII group (−4.6, 95% confidence interval [CI] −6.5 to −2.7; p = 0.001) and the BAU group (−2.5, 95% CI −4.6 to −0.4; p = 0.018), without significant difference between the groups (p = 0.080). There was no difference in migraine frequency between the groups (TeII: 1.0 day, 95% CI, −1.3 to 1.0; BAU: 1.0 day, 95% CI, −2.5 to 0.5; p = 0.718) or HURT-8 score (TeII: 10.5, 95% CI 9.5–11.5; BAU: 13.0, 95% CI 11.7–14.2; p = 0.053). There were no changes in the ISI score (TeII: 1.0, interquartile range [IQR] 6; p = 0.152; BAU: 0.5, IQR 4.5; p = 0.824), HADS-Anxiety score (TeII: −5, IQR 5.3; p = 0.186; BAU: 1.0, IQR 4.0; p = 0.445), or HADS-Depression score (TeII: 0.0, IQR 3.0; p = 0.163; BAU: 0.0, IQR 2.0; p = 0.303) in any of the groups. There was a higher degree of patient satisfaction in the TeII group compared with the BAU group in treatment (median [IQR] score 4 [3–5] vs. 3 [3–4], p < 0.001), headache improvement (median [IQR] 3 [2–4] vs. 2 [1–3], p = 0.002), the headache program (median [IQR] 4 [3–5] vs. 3 [3–4], p < 0.001), and information (median [IQR] 4 [3–5] vs. 3 [3–4], p = 0.005). Conclusion: Patients with migraine and/or TTH benefit from a telephone follow-up approach within the first 6 months of their treatment course in terms of more efficient treatment and higher patient satisfaction.