Obstructive sleep apnea (OSA) is a common condition associated with significant morbidity and health-care utilization. We determined the validity of an algorithm derived from administrative data for identifying OSA using the respiratory disturbance index (RDI) as the reference standard. We conducted a retrospective cohort study of adults in Alberta, Canada referred for facility and community-based sleep diagnostic testing between July 2005 and August 2007. Validity indices were estimated for several case definitions of OSA derived from outpatient physician billing claims and hospital discharge codes. For each algorithm, the sensitivity, specificity, positive predictive value (PPV) and negative predictive value (NPV) were calculated against several reference standards for OSA (RDI >= 5 h(-1), RDI >= 15 h(-1) or RDI >= 30 h(-1)). For the 2149 patients included in the study, an algorithm requiring one hospital discharge code or two outpatient billing claims identifying OSA in a 2-year period had a sensitivity of 24.1%, specificity of 67.8%, PPV of 74.8% and NPV of 18.3% (reference standard RDI >= 5 h(-1)). When comorbidities were included in the case definition, the specificity was 90.5% and PPV was 83.3% (reference standard RDI >= 5 h(-1)). Similar findings were observed using RDI >= 15 h(-1) and >= 30 h(-1) as the reference standard. We identify a claims-based algorithm that identifies OSA with a high degree of specificity in patients referred for sleep diagnostic testing. This validated algorithm has a good PPV and may be useful when identifying patients with OSA for population studies within a single-payer health-care system.