Background: Continuous positive airway pressure (CPAP) therapy is an efficacious treatment for patients diagnosed with obstructive sleep apnea (OSA). However, there are only few data on long-term adherence. The aim of this study is to quantify the extent of non-adherence and describe the clinical characteristics. Methods: A retrospective study including 695 patients with newly diagnosed OSA and prescribed CPAP therapy within an inclusion period of 14 months. All patients were offered free of charge individually adjusted CPAP therapy. Data on comorbidity, medication, BMI and Epworth Sleepiness Score (ESS) were obtained by questionnaires and consultation with an otorhinolaryngeal specialist. Results: The median follow-up time after initiating CPAP therapy was 3.0 (range 2.4–3.6) years. An adherence rate of 89% was found for severe OSA, 71% for moderate OSA and 55% for mild OSA. 18% initiated humidification. Patients adherent to CPAP had a significantly higher Body Mass Index (BMI), Apnea Hypopnea Index (AHI), Oxygen Desaturation Index (ODI) and ESS compared to non-adherent patients. Furthermore, adherence was associated with a higher frequency of observed interrupted breathing, a less frequent use of hypnotic drugs, fewer smokers, and they were more often offered humidification. Age, gender and comorbidity were not significantly associated with adherence. In a Cox model only AHI (Hazard Ratio (HR) 0.963, p < 0.001), ESS (HR 0.939, p = 0.001) and smoking (HR 1.576, p = 0.022) were independently associated with CPAP non-adherence. Conclusions: The severity of OSA, subjective daytime sleepiness and smoking status are independently related to adherence to CPAP therapy.