Objective: To determine the frequency of human papillomavirus (HPV) types and to assess bacterial vaginosis (BV) possible associations with cervical infections in indigenous Paraguayan women of the Department of Presidente Hayes. Methods: This study included 181 sexually active women without cervical lesions. HPV typing was performed by polymerase chain reaction with primers PGMY 09/11 followed by reverse line hybridization. BV was diagnosed by the Nugent criteria using the results from a Gram stain smear. Results: Sixteen percent of women were positive for at least one high risk HPV type (HR-HPV). The most frequent genotypes were HPV 16 (4.4%), followed by HPV 58 (3.3%), HPV 45 (3.3%), HPV 53 (2.8%) and HPV 11 (2.8%). A significant association between HR-HPV and BV was observed (p=0.01). In addition, women with BV had a higher frequency of Chlamydia trachomatis (p=0.0007), Trichomonas vaginalis (p=0.00009), Mycoplasma hominis (p=0.001). Conclusions: A large variety of HPV genotypes was detected and showed a slightly different pattern from previous studies on urban women in Paraguay, with the predominance of HR-HPV. Furthermore, the information of co-infections involved in BV could be useful for the improvement of national prevention programs, as well as for laboratory surveillance of these genital infections.