Papillomaviruses (PVs) are widespread pathogens. However, the extent of PV infections in bats remains largely unknown. This work represents the first comprehensive study of PVs in Iberian bats. We identified four novel PVs in the mucosa of free-ranging Eptesicus serotinus (EserPV1, EserPV2, and EserPV3) and Rhinolophus ferrumequinum (RferPV1) individuals and analyzed their phylogenetic relationships within the viral family. We further assessed their prevalence in different populations of E. serotinus and its close relative E. isabellinus. Although it is frequent to read that PVs co-evolve with their host, that PVs are highly species-specific, and that PVs do not usually recombine, our results suggest otherwise. First, strict virus-host co-evolution is rejected by the existence of five, distantly related bat PV lineages and by the lack of congruence between bats and bat PVs phylogenies. Second, the ability of EserPV2 and EserPV3 to infect two different bat species (E. serotinus and E. isabellinus) argues against strict host specificity. Finally, the description of a second noncoding region in the RferPV1 genome reinforces the view of an increased susceptibility to recombination in the E2-L2 genomic region. These findings prompt the question of whether the prevailing paradigms regarding PVs evolution should be reconsidered.