Background: Primary headache disorders and depression are two of the most common health problems that health professionals encounter. No previous epidemiological studies have investigated the relationship between these conditions in Saudi population. Objective: To evaluate the prevalence and correlates of major depression in patients with Primary headache disorders. Patients and Methods: Cross sectional study of randomly selected sample of patients with primary headache who were seen in neurology clinic in three tertiary care Centers in Aseer region. Data collected from medical records, which include relevant socio-demographic & clinical variables, headaches were classified based on the third edition of International Classification of Headache Disorders (ICDH-3 BETA) while Hamilton Depression Rating Scale (HAM-D) was used to assess depression. Results: 1025 subjects were included, with the mean age 29 ± 10 years, males 40.3% & females 59.7%. Those who met the criteria for migraine were 264 (25.8%) most of them were males (59.1%), married and older. 24.2% were diagnosed as probable migraine. Tension type headache was diagnosed in 293 patients (28.6%) while rest 21.4% had other type of headaches. Depression was prevalent in those with migraine 222 (84.1%) but surprisingly no clear association with severity noted and no difference when compared with those who did not meet the criteria for migraine of have other types of headache P=0.87 Odds ratio and 95% Cl=0.97 [0.66:1.4]. However, there were significant association between frequency of headaches and depression (P=0.001). Conclusion: Depression is common in patients with migraines and other types of headache. In our population depression was significantly associated with increase of the frequency of headaches regardless of severity of attacks.