Background: Postoperative de novo atrial fibrillation (POAF) is one of the most frequently encountered complications following cardiac surgery. Despite the identification of several risk factors, the link between sleep-disordered breathing (SDB) and POAF has barely been examined. The objective of this prospective observational study was to determine whether severe SDB is associated with POAF in patients after elective coronary artery bypass grafting (CABG) surgery. Study design and methods: The incidence and preoperative predictors of in-hospital POAF were assessed in 272 patients undergoing CABG surgery at the University Medical Center Regensburg (Germany). In-hospital POAF was detected by continuous telemetry-ECG monitoring and 12-lead resting ECGs within the first seven postoperative days. POAF that occurred after hospital discharge within 60 days post CABG surgery was classified as post-hospital POAF and was ascertained by standardized phone interviews together with the patients’ medical files, including routinely performed Holter-ECG monitoring at 60 days post CABG surgery. The night before surgery, portable SDB monitoring was used to assess the presence and type of severe SDB, defined by an apnea–hypopnea index ≥ 30/h. Results: The incidence of in-hospital POAF was significantly higher in patients with severe SDB compared to those without severe SDB (30% vs. 15%, p = 0.009). Patients with severe SDB suffered significantly more often from POAF at 60 days post CABG surgery compared to patients without severe SDB (14% vs. 5%, p = 0.042). Multivariable logistic regression analysis showed that severe SDB (odds ratio, OR [95% confidence interval, CI]: 2.23 [1.08; 4.61], p = 0.030), age ≥ 65 years (2.17 [1.04; 4.53], p = 0.038), and diabetes mellitus (2.27 [1.15; 4.48], p = 0.018) were significantly associated with in-hospital POAF. After additional adjustment for heart failure, the association between sleep apnea and postoperative atrial fibrillation was attenuated (1.99 [0.92; 4.31], p = 0.081). Conclusions: Amongst established risk factors, severe SDB was significantly associated with in-hospital POAF in patients undergoing CABG surgery. Whether SDB contributes to POAF independently of heart failure and whether risk for POAF may be alleviated by proper treatment of SDB merits further investigation.