Effectiveness of continuous positive airway pressure (CPAP) as a treatment of obstructive sleep apnea can be limited by poor compliance, but little is known about how to improve compliance. We performed a randomized, controlled clinical trial among 33 subjects of two interventions to improve compliance. One group of subjects received weekly phone calls to uncover any problems and encourage use, another received written information about sleep apnea and the importance of regular CPAP use, and a third served as control subjects. We found that intervention improved CPAP compliance (p = 0.059) and that the effect was particularly strong when intervention occurred during the first month of CPAP treatment (p = 0.004). Although the sample size did not allow definitive investigation of other explanatory variables, subjects with lower levels of education or those with relatives who used CPAP may have benefited from intervention more than other subjects. We conclude that simple, inexpensive efforts to improve compliance with CPAP can be effective, especially when applied at the start of CPAP treatment, but optimal intervention may vary with certain patient characteristics.