Objectives We investigated whether a specific exercise program for the neck–shoulder region reduces headache intensity, frequency, and duration, and how it influences neck disability among women with chronic headache compared to a control group. Design Two-center randomized controlled trial. Subjects 116 working-age women. Intervention The exercise group (n = 57) performed a home-based program with six progressive exercise modules, over 6 months. The control group (n = 59) underwent six placebo-dosed transcutaneous electrical nerve stimulation sessions. Both groups performed stretching exercises. Main measures The primary outcome was pain intensity of headache, assessed using the Numeric Pain Rating Scale. Secondary outcomes were frequency and duration of weekly headaches, and neck disability assessed using the Neck Disability Index. Generalized linear mixed models were used. Results Mean pain intensity at baseline was 4.7 (95% CI 4.4 to 5.0) in the exercise group and 4.8 (4.5 to 5.1) in the control group. After 6 months the decrease was slight with no between-group difference. Headache frequency decreased from 4.5 (3.9 to 5.1) to 2.4 (1.8 to 3.0) days/week in the exercise group, and from 4.4 (3.6 to 5.1) to 3.0 (2.4 to 3.6) in the control group (between-group p = 0.017). Headache duration decreased in both groups, with no between-group difference. Greater improvement in the Neck Disability Index was found in the exercise group (between-group change −1.6 [95% CI −3.1 to −0.2] points). Conclusion The progressive exercise program almost halved headache frequency. The exercise program could be recommended as one treatment option for women with chronic headache.