The heterogeneity of tinnitus is likely accounting for the lack of effective treatment approaches. Headaches have been related to tinnitus, yet little is known on how headaches impact tinnitus. We use cross-sectional data from the Swedish Tinnitus Outreach Project to i) evaluate the association between headaches and tinnitus (n = 1,984 cases and 1,661 controls) and ii) investigate the phenotypic characteristics of tinnitus subjects with tinnitus (n = 660) or without (n = 1,879) headaches. In a multivariable logistic regression model, headache was significantly associated with any tinnitus (odds ratio, OR = 2.61) and more so with tinnitus as a big problem (as measured by the tinnitus functional index, TFI ≥ 48; OR = 5.63) or severe tinnitus (using the tinnitus handicap inventory, THI ≥ 58; OR = 4.99). When focusing on subjects with tinnitus, the prevalence of headaches was 26% and reached 40% in subjects with severe tinnitus. A large number of socioeconomic, phenotypic and psychological characteristics differed between headache and non-headache subjects with any tinnitus. With increasing tinnitus severity, fewer differences were found, the major ones being vertigo, neck pain and other pain syndromes, as well as stress and anxiety. Our study suggests that headaches could contribute to tinnitus distress and potentially its severity.