Background: Exercise capacity reflects the cardiovascular risk after myocardial infarction (MI). The study aims to evaluate the impact of sleep-disordered breathing (SDB) on exercise capacity after MI. Methods: Consecutive patients referring to outpatient cardiac rehabilitation up to 28 days after MI and participating in the Polish Managed Care after Acute Myocardial Infarction (MC-AMI) program were included. On admission, we assessed the presence and the severity of SDB using the home sleep apnea test (HSAT), patients’ maximum exercise capacity on a treadmill exercise stress test (EST), and a 6-minute walk test (6MWT), as well as the effect of SDB on the results obtained. In the multivariate analysis, we verified the strength of the observed associations concerning age, anthropometric parameters, and left ventricular ejection fraction (LVEF). Results: A total of 254 patients aged 60.00 (interquartile range 51.00–67.00), including 39 (15.4%) women, with technically adequate HSAT, constituted the study group. Mild SDB was found in 82 (32.3%), moderate in 54 (21.3%), and severe in 51 (20.1%) patients. Among those diagnosed with SDB, obstructive sleep apnea (OSA) was dominant in 167 (89.8%). With the worsening of SDB, the distance in 6MWT and the maximum physical exertion achieved in EST, expressed in metabolic equivalents (METs) and maximal heart rate (MHR), decreased. The linear regression analysis confirmed the following: (1) inversely proportional relationship between the respiratory event index and METs, MHR, and 6MWT distance (p = 0.005, p = 0.008, and p = 0.004), and the maximum apnea duration and MET and 6MWT distance (p = 0.042 and p = 0.002); and (2) directly proportional relationship between mean arterial oxygen saturation (SpO{}_2) during sleep and MET, MHR, and 6MWT distance (p = 0.019, p = 0.006, and p = 0.013), and minimum SpO{}_2 and MET and MHR (p = 0.040 and p 0.001). However, the independent risk factors for impaired exercise capacity, determined using multivariable regression analysis, were age, female sex, higher body mass index (BMI), and decreased LVEF, but not SDB parameters. Conclusions: SDB negatively impacts exercise capacity after MI. However, the strength of this association may be less pronounced due to the interaction of risk factors common for SDB and impaired exercise capacity, e.g., sex, age, BMI, and LVEF.