Background: Human papillomavirus (HPV) infection is a prerequisite of cervical cancer, the leading cause of cancer mortality in Ethiopian women today. Data on Ethiopian cervical HPV prevalence and genotype distribution are rare, but essential as pre-vaccine baseline data to monitor changes after initiating HPV vaccination. The objectives of this study were to assess the cervical HPV prevalence, genotype distribution and associated correlates among female hospital outpatients in rural Ethiopia. Methods: We examined a consecutive sample of 537 women 15–64 years of age in rural Ethiopia between November and December 2006. Screening for low risk (LR) and high-risk (HR) cervical HPV infection was performed and HR positive samples were genotyped with a GP5+/6 + − and SPF10-primer based system. Results: The age-standardized prevalence of HPV, HPV HR and HPV LR infection was 17.3% (95% CI 14.1-20.5), 15.8% (95% CI 12.7-18.9) and 3.9% (95% CI 2.3-5.6), respectively. Among HC2 HPV HR positive infections (n = 86), the most common genotype was HPV 16 (24.4%), followed by 52 (11.6%), 56 (10.5%) and 31 (10.5%). Non-married relationship and widowhood, increasing number of lifetime sexual partners, human immunodeficiency virus infection and non-traditional housing type, but not age, were significantly associated with HR HPV infection. Conclusions: These results on cervical HPV prevalence and genotype distribution may serve as baseline data in evaluating the impact of future HPV vaccination programmes in rural Ethiopia.