Background. Human Papilloma Virus (HPV) infection is the most common sexually transmitted viral infection worldwide. HPV is highly prevalent in sexually active men who have sex with men (MSM) and has been associated with anal cancer, penile cancer, and oropharyngeal cancer. Methods. From March to September 2011, we conducted a cross-sectional study of HPV prevalence among MSM above age 18 years. Participants were recruited using respondent driven sampling at Clinica Cayetano Heredia. All participants provided anal, genital, and oral samples for HPV DNA testing, and blood for HIV and HPV antibody testing. Results. A total of 200 MSM were recruited in the study. The mean age was 34 years (range 18-59 years, SD = 9.4) and 101 participants were HIV negative (99 HIV positive). HPV 6/11/16/18 or quadrivalent HPV vaccine (HPV4) genotype seroprevalence among HIV negative and positive MSM was 64.3% (55%-75.9%) and 93.8%(87.6%-99.2%) respectively (p<0.001). HIV positivity was associated with a higher prevalence of HPV4 and HPV 16/18 DNA at external genital sites and the anal canal. HPV4 DNA prevalence at external genital sites among HIV negative and positive MSM was 14.9% and 28.7% (p = 0.02) respectively, at anal canal was 50.9% and 79.0% (p = 0.001), and at the oral cavity was 9.9% and 8.5% (p = 0.6). Conclusions. HPV4 seroprevalence was high in our study among both HIV positives and negatives, with HPV DNA prevalence much lower, and the anal canal being the anatomical site with the highest HPV DNA prevalence. HPV prevention interventions are needed among MSM at high-risk for HIV infection.