Currently available prophylactic vaccines have no therapeutic efficacy for preexisting human papillomavirus (HPVs) infections, do not target all oncogenic HPVs and are insufficient to eliminate the burden of HPV induced cancer. We aim to develop an alternative HPV vaccine which is broadly effective and capable of clearing preexisting infection. In an initial attempt to develop a broadly reactive therapeutic vaccine, we designed a putative papillomavirus (PV) ancestor antigen (circulating sequence derived antigenic sequences E1E2—CDSE1E2) based on the conserved E1 and E2 protein sequences from existing oncogenic HPV strains. This antigen was found to be as related to circulating oncogenic Macaca fascicularis papillomaviruses (MfPVs) as to oncogenic HPVs. The CDSE1E2 antigen was fused to a T-cell adjuvant and encoded in chimpanzee 3 and 63 adenoviral vectors. We first showed that the combination of these 2 vaccines induced long-lasting potent CDSE1E2 specific T cell responses in outbred mice. This prime-boost regimen was then tested in female macaques naturally infected with MfPVs. All immunized animals (16/16) responded to the vaccine antigen but with reduced cross-reactivity against existing PVs. Preexisting MfPV infections did not prime vaccine inducible immune responses. Importantly, immunized oncogenic MfPV type 3 (MfPV3) infected animals that responded toward MfPV3 were able to diminish cervical MfPV3 DNA content. Although insufficient breadth was achieved, our results suggest that a relevant level of E1E2 specific T cell immunity is achievable and might be sufficient for the elimination of PV infection. Importantly, naturally infected macaques, offer a relevant model for testing vaccines aimed at eliminating mucosal PV infections.