Background: This study addressed the hypothesis that cardiovascular reactivity during graded bicycle exercise is influenced by a coexisting sleep-related breathing disorder (SRBD). Methods: Blood pressure and heart rate were assessed at rest and during graded exercise (110 W and maximal load) in 1,149 patients of a Sleep Disorders Center. The degree of SRBD, and potential confounders, including blood gases and pulmonary function, were determined. Results: Maximal exercise capacity tended to decrease with SRBD activity (p = 0.07). The heart rate reactivity was blunted and reduced by –0.07 and –0.09 beats/min for every SRBD unit at 110 W (p < 0.001) and at maximal load (p < 0.001), respectively. Systolic and diastolic blood pressure reactivity at maximal load were positively associated with SRBD severity. These associations were independent of possible confounders. Conclusion: SRBD is associated with reduced physical working capacity and a modified hemodynamic response to exercise.