BACKGROUND: Women with HIV infection have a higher risk for cervical squamous intraepithelial lesions than do women without HIV infection, and the optimal regimen for cervical cancer screening in these women is uncertain. OBJECTIVE: To assess the net health consequences, costs, and cost-effectiveness of various screening strategies for cervical neoplasia and cancer in HIV-infected women. DESIGN: A cost-effectiveness analysis from a societal perspective done by using a state-transition Markov model. Values for incidence, progression, and regression of cervical neoplasia; efficacy of screening and treatment; progression of HIV disease; mortality from HIV infection and cancer; quality of life; and costs were obtained from the literature. SETTING: Simulated clinical practice in the United States. PATIENTS: HIV-infected women representative of the U.S. population. INTERVENTION: Six main screening strategies--no screening, annual Papanicolaou smears, annual Papanicolaou smears after two negative smears obtained 6 months apart (recommended by the Centers for Disease Control and Prevention), semiannual Papanicolaou smears, annual colposcopy, and semiannual colposcopy--were considered. MEASUREMENTS: Quality-adjusted life-years (QALYs), lifetime costs, and incremental cost-effectiveness. RESULTS: Annual Papanicolaou smear screening resulted in a 2.1-month gain in quality-adjusted life expectancy for an incremental cost of $12,800 per QALY saved. Annual Papanicolaou smear screening after two negative smears obtained 6 months apart provided an additional 0.04 QALYs at a cost of $14,800 per QALY saved. Semiannual Papanicolaou smear screening provided a further 0.17 QALYs at a cost of $27,600 per QALY saved. Annual colposcopy cost more but provided no additional benefit compared with that given by semiannual Papanicolaou smear screening, and semiannual colposcopy exceeded $375,000 per QALY saved. Results were most sensitive to the rate of progression of neoplasia to invasive cancer. CONCLUSIONS: In HIV-infected women, cervical cancer screening with annual Papanicolaou smears after two negative smears obtained 6 months apart offers quality-adjusted life expectancy benefits at a cost comparable to that of other clinical preventive interventions.