Due to the recent widespread availability of highly active antiretroviral therapy (HAART) in middle-income countries, there has been an increase in life expectancy for women on HAART, but no corresponding decrease in cervical cancer incidence. This study evaluates the optimal cervical cancer screening strategy for HIV-infected women in a middle-income country. We developed a mathematical model, which simulates the natural history of the HPV infection, as well as the HIV-mediated immunosupression among women in Brazil. Our model was calibrated using data from the IPEC/FIOCRUZ Women's HIV-infected cohort. The model compares the lifetime effects, costs and cost-effectiveness of strategies combining cytology, HPV DNA test and colposcopy at different screening intervals for different CD4 count strata (27 strategies in total). We found that the strategy with the best cost-effectiveness profile (cost-effectiveness ratio-U$4,911/year of life saved [YLS] and probability of being cost-effective-86%) was HPV testing followed by cytology triage every year for all HIV infected women, considering a very cost-effective threshold given by Brazil's GDP per capita (US$8,625/YLS). The results were robust to changes in the input parameters as demonstrated in one-way, scenario, threshold and probabilistic sensitivity analysis. Our study indicates that annual HPV testing followed by cytology triage for all HIV-infected women is likely to be very cost-effective in a middle-income country like Brazil. The results reflect the synergic effect of using a highly sensitive screening test (HPV DNA test) in sequence with a highly specific test (cytology).