Background: Cervical cancer is currently the third most common female cancer in Malaysia , with the human papillomavirus (HPV) considered as one of the important contributory factors. This study was conducted to determine HPV prevalence, its genotype distribution, and other potential risk factors among women in Kota Kinabalu, Sabah in order to evaluate the likely efficacy of current HPV vaccines in the local population. Methods: A total of 240 cervical samples were collected and subjected to DNA extraction, PCR amplification using the MY09/MY11 primer pair, and restriction fragment length polymorphism (RFLP) for HPV detection and genotyping. Sociodemographic, clinical, and behavioural data were also collected via questionnaires. Results: The prevalence of HPV infection was 9.6%. The most common HPVs among 13 genotypes were high-risk HPV-56 (16.7%) and probable high-risk HPV-70 (16.7%) followed by HPV-16, -58, -53, -61, -33, -59, and -66 (in decreasing order of prevalence) including the rare genotypes: HPV-62, -81, -82 and -84. Statistical analyses using logistic regression models showed that HPV infection was significantly associated with employment (OR 4.94; CI 1.58-15.40) and education at secondary/high school level (OR 0.13; CI 0.03-0.62). Conclusion: Distribution of HPV genotypes in Sabah indicated a high prevalence of HPV-56 and -70 which are among the rare HPV types in West Malaysia and merit consideration in future strategies for HPV vaccination specifically for local Sabahan women.