Background: Several studies have demonstrated an association between headache and disturbed sleep. None have examined this association across the headache spectrum. Our goal was to determine whether migraine and migraine with aura differ from nonmigraine headache in terms of associated insomnia complaints or severity of sleep problems. Methods: A probability sample of US adults was used. A structured interview administered by trained interviewers was used. Diagnostic criteria for migraine and migraine with aura were based on the International Headache Society classification. The presence or absence of four forms of sleep disturbance associated with an insomnia diagnosis was ascertained. Results: There was a significant association between frequent severe headache, including migraine with and without aura, and disordered sleep. Adults with headache reported more frequently difficulty initiating sleep (odds ratio [confidence interval] = 2.0 [1.6–2.5]), difficulty staying asleep (2.5 [2.1–3]), early morning awakening (2.0 [1.7–2.5]) and daytime fatigue (2.6 [2.2–3.2]) and also were more than twice as likely to report three or more of these symptoms(2.5 [2–3.1]) compared to the individuals without headache. Discussion: Adults with severe headache are at significantly higher risk of also suffering from sleep problems, when compared with the general population, regardless of specific headache type. Optimal treatment of headache must include investigation for sleep disorders and vice versa.