Background and Objectives: Poor sleep quality in patients with obstructive sleep apnea (OSA) may be associated with different clinical and polysomnographic features. The aim of this study was to identify features associated with poor sleep quality in OSA patients. Materials and Methods: This was a cross-sectional study enrolling patients with OSA confirmed by polysomnography (PSG). In addition to gathering clinical data, patients were assessed using the Pittsburgh Sleep Quality Index (PSQI), the Epworth Sleepiness Scale (ESS), and the Clinical Global Impression Scale. Univariate and multivariable analyses were performed to identify factors associated with an increased risk of poor sleep quality in this population. Results: Among 505 enrolled patients (mean age of 57.1 years, 69.7% male) poor quality of sleep (PSQI score ≥ 5) was confirmed in 68.9% of them. Multivariable analysis revealed the following factors associated with poor sleep quality: chronic heart failure (OR 3.111; 95% CI, 1.083–8.941, p = 0.035), male sex (OR 0.396; 95% CI, 0.199–0.787, p = 0.008), total ESS score (OR 1.193; 95% CI, 1.124–1.266, p p = 0.036), and N3 percentage of total sleep time (OR 1.110; 95% CI, 1.027–1.200, p = 0.009). Conclusions: Our study suggests that both the female sex and coexistence of heart failure are independent risk factors for poor sleep quality. Moreover, we hypothesize that nocturnal hypoxia may lead to a misperception of sleep quality and may explain the counterintuitive association between a higher proportion of deep sleep and poor sleep quality.