Background: Sleep-disordered breathing (SDB) is common among acute stroke patients. We sought to investigate the prevalence, severity and type of SDB in consecutive acute stroke patients. Moreover, we aimed to identify independent predictors of SDB in the acute stroke setting and investigate potential associations between SDB and functional outcomes at three months. Methods: We prospectively studied consecutive acute stroke patients, who underwent overnight polysomnography within 72 h from symptom onset. Demographics, clinical and imaging characteristics were documented. Daytime sleepiness preceding the stroke, stroke severity on admission and functional outcome at three months were evaluated using the Epworth-Sleepiness Scale (ESS), National Institute of Health Stroke Scale (NIHSS) and modified Rankin Scale (mRS), respectively. SDB was documented using standard polysomnography criteria. Results: A total of 130 consecutive acute stroke patients were prospectively evaluated [110 with ischemic stroke and 20 with intracerebral hemorrhage, mean age 60.5 ± 10.9 years, 77% men, median NIHSS score on admission: 3 (IQR: 2–17)]. The rate of SDB detection on polysomnography recordings was 79% (95% CI: 71–86). Three variables were independently associated with the likelihood of SDB detection in multivariable analyses adjusting for potential confounders: age (OR per 10-year-increase: 2.318, 95% CI: 1.327–4.391, p = 0.005), male sex (OR: 7.901, 95% CI: 2.349–30.855, p = 0.001) and abnormal ESS-score (OR: 6.064, 95% CI: 1.560–32.283, p = 0.017). Among patients with SDB, congestive heart failure was independently associated with the likelihood of central apnea detection (OR: 18.295, 95% CI: 4.464–19.105, p < 0.001). Among all patients, increasing NIHSS score on admission (OR: 0.817, 95% CI: 0.737-0.891, p < 0.001) and Apnea–Hypopnea Index (OR: 0.979, 95% CI: 0.962–0.996, p = 0.020) emerged as independent predictors of excellent functional outcome at 3 months (mRS-scores 0–1). Conclusion: The high prevalence and severity of SDB in acute stroke patients and its negative impact on functional outcome indicate the importance of polysomnography implementation in everyday clinical practice of acute stroke work-up and management.