The association between sleep apnea (SA) and depression had been reported in a few previous studies. However, whether SA increases the risk of major depressive disorder (MDD) has not been studied comprehensively in a large-scale study. We performed this population-based cohort study to assess the association between SA and MDD. We identified adult patients having SA from the Taiwan National Health Insurance Research Database and excluded those having MDD before SA diagnosis. Thirty control subjects were randomly selected to match to each SA patient by age and sex. Totally, 10,259 SA patients were matched to 102,590 control subjects. The incidence rate and cumulative incidence of MDD were significantly higher in SA patients than in the control subjects (both p < 0.0001). Multivariable Cox regression analysis showed that SA remained an independent risk factor for incident MDD after adjusting for age, sex, residency, income level, and comorbidities (hazard ratio = 2.9 [95% CI 2.8-3.1], p < 0.0001). In summary, SA patients have an increased risk to develop MDD. Physicians caring for SA patients must pay attention to their psychosocial health status.