Objectives: To investigate the prevalence of high-risk (HR) human papillomavirus (HPV) and factors associated with HR-HPV infection among women from rural Eastern Cape, South Africa. Methods: HPV prevalence was determined by Hybrid Capture 2 assay in cervical specimens from 417 women aged ≥30 years (median 46 years) recruited from the community health clinic in the Eastern Cape. Results: HR-HPV prevalence was 28.5% (119/417), and HIV-positive women had significantly higher HR-HPV prevalence than HIV-negative women (40.6%, 63/155 vs 21.4%, 56/262, respectively; p = 0.001). HIV-positive status (odds ratio (OR) 2.52, 95% confidence interval (CI) 1.63–3.90), having ≥3 lifetime sexual partners (OR 2.12, 95% CI 1.16–3.89), having ≥1 sexual partner in the last month (OR 1.89, 95% CI 1.21–2.92), ≥4 times frequency of vaginal sex in the past 1 month (OR 2.40, 95% CI 1.32–4.35), and having a vaginal discharge currently/in the previous week (OR 2.13, 95% CI 1.18–3.85) increased the risk of HR-HPV infection. In the multivariate analysis, HIV positivity remained strongly associated with HR-HPV infection (OR 1.94, 95% CI 1.17–3.22). Conclusions: Risk factors related to sexual behaviors play a significant role in HR-HPV infection in this population. This report will inform health policymakers on HPV prevalence and contribute to discussions on the use of HPV testing as the primary cervical cancer screening test in South Africa.