Persistent human papillomavirus (HPV) infection is considered the primary etiological factor for invasive cervical cancer. Understanding the epidemiology of circulating potential high-risk (HR) and HR HPV strains is essential in updating epidemiological knowledge and recommendations on genotype-specific vaccination development. This study determined the prevalence and factors associated with Potential HR/HR HPV among women attending selected reproductive health clinics in Lake Victoria Basin. A cross-sectional facility-based survey made up of 434 women aged 16–68 years was carried out in two selected facilities. Structured questionnaires were administered to collect participant clinical and social characteristics. Cervical specimens were collected and HPV genotyping was carried out using RIATOL HPV genotyping qPCR assay. Descriptive statistics followed by logistic binary regression was done using R version 4.3.2. The overall prevalence of potential HR/HR HPV among women attending the selected reproductive health clinics was reported at 36.5% (158/434). Specifically, in the rural setting, Gobei Health Center, the prevalence was 41.4% (41/99) while in the urban setting-JOOTRH, it was 34.6% (117/335). The most prevalent potential HR/HR HPV are 52, 67, 16, 31, 39, 45, and 31 among women. Age was the main factor associated with HPV infection with women between the age of 30–39 having the highest risk (AOR=0.3, CI: 0.2–0.7, p Age was the main factor associated with HPV infection with women between the age of 30–39 having the highest risk (AOR=0.3, CI:0.2–0.7, p<0.001).In both rural and urban regions, potential HR/HR HPV infection among women attending reproductive health clinics at the selected facilities remains common. The study identifies the need for effective implementation and clinical follow-up process of cervical cancer control program in the LVB.