The objective was to investigate symptoms of depression and anxiety in relation to the presence and severity of obstructive sleep apnea (OSA) among patients referred with suspicion of OSA. The sample comprised 3770 consecutive patients with a mean age of 49.1 years; 69.7% were male. OSA was diagnosed and categorized based on a standard respiratory polygraphic sleep study using a type 3 portable monitor. Patients completed the validated Hospital Anxiety and Depression Scale (HADS) prior to the sleep study. In addition, they answered questions about whether they were currently in treatment for mental disorders and whether they had been diagnosed previously with depression. We adjusted for sex, age, smoking, alcohol consumption and obesity in the logistic regression analyses. In total, 35.1% had apnea–hypopnea index (AHI) < 5 (no OSA), 31.9% had AHI: 5–14.9 (mild OSA), 17.3% had AHI: 15–29.9 (moderate OSA) and 15.7% had AHI ≥ 30 (severe OSA). The prevalence of anxiety and depressive symptoms were significantly lower with increased OSA severity, and also when adjusting for sex, age, smoking, alcohol consumption and obesity (AHI ≥ 15 as dependent variable). Similarly, currently being in treatment for mental disorders and being diagnosed previously with depression were both associated negatively with OSA severity, with only the latter remaining significant in the fully adjusted model. Furthermore, multiple linear regressions showed that HADS anxiety and depression total scores were associated negatively with AHI. In conclusion, symptoms of anxiety and depression were associated negatively with OSA severity in these referred patients. The findings remained significant also after adjusting for several relevant confounders.