Background: Men who have sex with men (MSM) are at high risk for human papillomavirus (HPV)-related anal cancer. Little is known about the prevalence of low-grade squamous intraepithelial lesions (LSILs) and the anal cancer precursor, high-grade squamous intraepithelial lesions (HSILs), among young MSM with HIV (MSMLWH). HPV vaccination is recommended in this group, but its safety, immunogenicity, and protection against vaccine-Type HPV infection and associated LSILs/HSILs have not been studied. Methods: Two hundred and sixty MSMLWH aged 18-26 years were screened at 17 US sites for a clinical trial of the quadrivalent (HPV6,11,16,18) HPV (qHPV) vaccine. Those without HSILs were vaccinated at 0, 2, and 6 months. Cytology, high-resolution anoscopy with biopsies of lesions, serology, and HPV testing of the mouth/penis/scrotum/anus/perianus were performed at screening/month 0 and months 7, 12, and 24. Results: Among 260 MSMLWH screened, the most common reason for exclusion was detection of HSILs in 88/260 (34%). 144 MSMLWH were enrolled. 47% of enrollees were previously exposed to HPV16. No incident qHPV type-Associated anal LSILs/HSILs were detected among men naive to that type, compared with 11.1, 2.2, 4.5, and 2.8 cases/100 person-years for HPV6,11,16,18-Associated LSILs/HSILs, respectively, among those previously exposed to that type. qHPV was immunogenic and safe with no vaccine-Associated serious adverse events. Conclusions: 18-26-year-old MSMLWH naive to qHPV vaccine types were protected against incident qHPV type-Associated LSILs/HSILs. Given their high prevalence of HSILs, there is an urgent need to vaccinate young MSMLWH before exposure to vaccine HPV types, before initiating sexual activity, and to perform catch-up vaccination.