Cervical cancer remains a significant cause of morbidity and mortality in women worldwide and is the leading cause of cancer-related death in Botswana. It is well established that women with HIV have a higher risk of persistent HPV infection leading to cervical cancer. We assessed HPV prevalence and genotype distribution in 126 tissue specimens from confirmed invasive cervical cancer cases using Abbott real-time PCR assay. Overall, 88 (69.8%) women were HIV-infected. Fifty-seven (64.8%) of the HIV-infected women had a baseline CD4+ count ≥350 cells/μl, and 82 (93.2%) were on antiretroviral therapy at the time of cervical cancer diagnosis. The median age of HIV-infected patients was significantly younger than that of HIV-uninfected patients (p < 0.001). HPV DNA was detected in all of 126 (100%) of tissues analyzed in our study. The HPV genotypes identified included the HPV-16 (75.4%), HPV-18 (28.6%) and other high-risk (hr) HPV genotypes (16.7%). HIV infection was positively associated with the presence of the HPV-16 genotype (p = 0.036), but not with HPV-18 or with other high-risk (hr)-HPV genotypes. Thirty-three percent of the patients had multiple hr-HPV genotypes, with higher rates in HIV-infected women. These results highlight the importance and potential impact of large-scale HPV vaccination programs covering HPV-16 and HPV-18 genotypes in countries like Botswana with high burden of HIV infection.