Background Cervical cancer (CC) is one of the leading causes of cancer mortality among women from Paraguay, with high incidence and mortality rates (31.2 and 16 per 100 000 women, respectively). Although the risk factors associated with high-risk human papillomavirus (hrHPV) infection and preneoplastic cervical lesions are widely studied, population-based characteristics of particular settings may influence the feasibility of HPV-based CC screening implementation. This study aimed to explore factors associated with hrHPV infection and high-grade cervical neoplasia in hrHPV-positive (hrHPV+) women from Paraguay. Methods A total of 5677 women aged 30–64 years from the Central Department of Paraguay were screened with HPV test (Hybrid Capture 2) and Pap smear. Sociodemographic and risk factor interviews were conducted. hrHPV+ women were referred to colposcopy and women with an abnormal colposcopy had a biopsy taken. The outcomes recorded were the hrHPV status and the presence of high-grade cervical intraepithelial neoplasia or worse (CIN2+) among hrHPV+ women. Associations were investigated using multivariate logistic regressions. Results hrHPV prevalence was 13.8% (95%CI 13.0–14.8). This value decreased with the age of women (p-trend<0.001) and increased with the lifetime number of sexual partners (p-trend<0.001) and number of previous female partners of their current male partner if women had had one lifetime sexual partner (p-trend<0.001), increasing from 3.06 (95%CI 0.073–20.9) if partners had had one previous female partner to 9.19 (95%CI 2.36–61.1) if they had had eight or more. In hrHPV+ women, CIN2+ prevalence was 10.7% (95%CI 8.58–13.2) and increased with time since the last Pap smear (p-trend<0.001) and with the increasing number of pregnancies (p-trend = 0.05). Conclusion In these settings, the sexual behavior of women and their male partners is associated with hrHPV infection. In hrHPV+ women, underscreening practices and multiple pregnancies are associated with CIN2+. This knowledge can contribute to public health policies for CC prevention and control in Paraguay.