Background: Although human papillomavirus (HPV) infection in heterosexual couples has been sparsely studied, it is relevant to understand disease burden and transmission mechanisms. The present study determined the prevalence and concordance of type-specific HPV infection as well as the determinants of infection in heterosexual couples in a rural area of Mexico. Methods: A cross-sectional study was conducted in 504 clinically healthy heterosexual couples from four municipalities in the State of Mexico, Mexico. HPV testing was performed using biotinylated L1 consensus primers and reverse line blot in cervical samples from women and in genital samples from men. Thirty-seven HPV types were detected, including high-risk oncogenic types and low-risk types. Multivariate logistic regression models were utilized to evaluate factors associated with HPV. Results: The prevalence of HPV infection was 20.5% in external male genitals and 13.7% in cervical samples. In 504 sexual couples participating in the study, concordance of HPV status was 79%; 34 partners (6.7%) were concurrently infected, and 21 out of 34 partners where both were HPV positive (61.8%) showed concordance for one or more HPV types. The principal risk factor associated with HPV DNA detection in men as well as women was the presence of HPV DNA in the respective regular sexual partner (OR = 5.15, 95% CI 3.01-8.82). In men, having a history of 10 or more sexual partners over their lifetime (OR 2.5, 95% CI 1.3 - 4.8) and having had sexual relations with prostitutes (OR 1.7, 95% CI 1.01 - 2.8) increased the likelihood of detecting HPV DNA. Conclusions: In heterosexual couples in rural regions in Mexico, the prevalence of HPV infection and type-specific concordance is high. High-risk sexual behaviors are strong determinants of HPV infection in men.