The aim of this large cross-sectional population-based study was to examine the association between migraine, non-migrainous headache and headache frequency with depression, and anxiety disorders. From 1995 to 1997, all 92 566 inhabitants aged 20 years and above in Nord-Trøndelag County in Norway were invited to participate in the Nord-Trøndelag Health Study ('Helseundersøkelsen i Nord-Trøndelag' = HUNT-2). A total of 64 560 participated, whereof 51 383 subjects (80%) completed a headache questionnaire that was included. Of these 51 383 individuals, 47 257 (92%) completed the depression subscale items and 43 478 (85%), the anxiety subscale items of the Hospital Anxiety and Depression Scale (HADS). Associations were assessed in multivariate analyses, estimating prevalence odds ratios (OR) with 95% confidence intervals (CI). Depression and anxiety disorders as measured by HADS, were significantly associated with migraine (OR = 2.7, 95% CI 2.3-3.2; OR = 3.2, 95% CI 2.8-3.6) and non-migrainous headache (OR = 2.2, 95% CI 2.0-2.5; OR = 2.7, 95% CI 2.4-3.0) when compared with headache-free individuals. The association was stronger for anxiety disorders than for depression. The ORs for depression and anxiety disorders amongst both migraine and non-migrainous sufferers increased with increasing headache frequency. Depression and anxiety disorders are associated with both migraine and non-migrainous headache, and this association seems more dependent on headache frequency than diagnostic category.