Infection by human papillomavirus (HPV) type 16, the most oncogenic HPV type, was found to be the least affected by HIV-status and CD4 count of any of the approximately 13 oncogenic HPV types. This relative independence from host immune status has been interpreted as evidence that HPV16 may have an innate ability to avoid the effects of immunosurveillance. However, the impact of immune status on other individual HPV types has not been carefully assessed. We studied type-specific HPV infection in a cohort of 2,470 HIV-positive (HIV[+]) and 895 HIV-negative (HIV[−]) women. Semi-annually collected cervicovaginal lavages were tested for >40 HPV types. HPV type-specific prevalence ratios (PRs), incidence and clearance hazard ratios (HRs), were calculated by contrasting HPV types detected in HIV[+] women with CD4 < 200 to HIV[−] women. HPV71 and HPV16 prevalence had the weakest associations with HIV-status/CD4 count of any HPV, according to PRs. No correlations between PRs and HPV phylogeny or oncogenicity were observed. Instead, higher HPV type-specific prevalence in HIV[−] women correlated with lower PRs (ρ = −0.59; p = 0.0001). An alternative (quadratic model) statistical approach (PHIV+ = a*PHIV− + b*PHIV− 2; R2 = 0.894) found similar associations (p = 0.0005). In summary, the most prevalent HPV types in HIV[−] women were the types most independent from host immune status. These results suggest that common HPV types in HIV[−] women may have a greater ability to avoid immune surveillance than other types, which may help explain why they are common.