Background: HIV-1-positive patients clear the human papillomavirus (HPV) infection less frequently than HIV-1-negative. Datasets for estimating HPV clearance probability often have irregular measurements of HPV status and risk factors. A new transitional probability-based model for estimation of probability of HPV clearance was developed to fully incorporate information on HIV-1-related clinical data, such as CD4 counts, HIV-1 viral load (VL), highly active antiretroviral therapy (HAART), and risk factors (measured quarterly), and HPV infection status (measured at 6-month intervals). Methodology and Findings: Data from 266 HIV-1-positive and 134 at-risk HIV-1-negative adolescent females from the Reaching for Excellence in Adolescent Care and Health (REACH) cohort were used in this study. First, the associations were evaluated using the Cox proportional hazard model, and the variables that demonstrated significant effects on HPV clearance were included in transitional probability models. The new model established the efficacy of CD4 cell counts as a main clearance predictor for all type-specific HPV phylogenetic groups. The 3-month probability of HPV clearance in HIV-1-infected patients significantly increased with increasing CD4 counts for HPV16/16-like (p<0.001), HPV18/18-like (p<0.001), HPV56/56-like (p = 0.05), and low-risk HPV (p<0.001) phylogenetic groups, with the lowest probability found for HPV16/16-like infections (21.60±1.81% at CD4 level 200 cells/mm 3, p<0.05; and 28.03±1.47% at CD4 level 500 cells/mm 3). HIV-1 VL was a significant predictor for clearance of low-risk HPV infections (p<0.05). HAART (with protease inhibitor) was significant predictor of probability of HPV16 clearance (p<0.05). HPV16/16-like and HPV18/18-like groups showed heterogeneity (p<0.05) in terms of how CD4 counts, HIV VL, and HAART affected probability of clearance of each HPV infection. Conclusions: This new model predicts the 3-month probability of HPV infection clearance based on CD4 cell counts and other HIV-1-related clinical measurements. © 2012 Kravchenko et al.