Background: Human papillomavirus (HPV) vaccination programs are a key intervention in protecting individuals against HPV-related disease. HIV1-infected individuals are at increased risk of HPV-associated cancers. This study was conducted to evaluate the potential role of prophylactic HPV vaccines in preventing new HPV infections among participants with perinatally acquired HIV who received the quadrivalent HPV vaccine at least five years before this study. Methods: This cross-sectional study was conducted at Newlands Clinic, Harare, Zimbabwe. The clinic provided the Gardasil quadrivalent HPV vaccine (4vHPV) to 624 adolescents living with HIV starting in December 2015. Vaginal and penile swabs were collected and tested for HPV types from the study participants who had received the 4vHPV vaccine 5–6 years before enrolment. Results: We present the results of 98 participants (44.6% female) vaccinated at a median age of 15 years (IQR 12–16). The mean amount of time since vaccination was 6 years (SD: ±0.4). The HPV-positive rate amongst the analyzed swabs was 69% (68/98). Among 30/98 (31%) HPV-positive participants, 13/98 (13%) had low-risk HPV types, and 17/98 (17%) had high-risk HPV types. Twelve participants tested positive for HPV18, only one participant tested positive for HPV16, and an additional four (4.3%) tested positive for either type 6 or 11, with respect to vaccine-preventable low-risk HPV types. Conclusion: The Gardasil quadrivalent HPV vaccine (4vHPV) was expected to protect against infection with HPV types 16, 18, 6, and 11. We demonstrated a possible waning of immunity to HPV18 in 17% of the participants, and an associated loss in cross-protection against HPV45. We observed a relatively high prevalence of ‘opportunistic non-vaccine HPV types’ or ‘ecological niche occupiers’ in this cohort, and suggest further research on the involvement of these types in cervical and other genital cancers. Our study is one of the few, if not the first, to report on HPV vaccine immunoprotection among people living with HIV (PLWH), thereby setting a baseline for further studies on HPV vaccine effectiveness among PLWH.