Human papillomavirus (HPV) infection is a common viral sexually transmitted infection and the main cause of cervical cancer in women worldwide. Epidemiological data on the prevalence of HPV in a given population is essential for the establishment of effective prevention strategies. The aim of this study was to determine HPV prevalence in women who attended a public health service within an urban center in Brazil. Cervical samples were collected from 337 women recruited from a primary public health care clinic in the city of Cruz Alta located in Rio Grande do Sul, the southernmost State of Brazil. Samples were analyzed for HPV DNA and with Pap smear screening tests. HPV was detected in 114 (34%) women. HPV type analysis revealed that 95 (83.3%) of those represented infections with a single genotype, while 19 (16.7%) were mixed genotype infections. High- and low-risk HPV genotypes were detected in 83 (72.8%) and 48 (42.1%) samples, respectively. Furthermore, a great diversity of HPV genotypes was observed (18 high-risk, 12 low-risk, and 1 indeterminate). The most commonly identified low-risk types were candHPV62 (7.9%) and 61 (5.3%), while the most common high-risk types were 16 and 33 (8.8% each). Abnormal cytology was observed in 10 (3.0%) women, 9 of which were infected with HPV. Of the remaining 327 women with normal cytology results, 107 (32.7%) were positive for HPV DNA. HPV infection was correlated with younger age (less than 40 years), a first Pap smear, and other vaginal infections.