The associations between pathogens and their hosts are complex and can result from a variety of evolutionary processes including codivergence, lateral transfer, or duplication. Papillomaviruses (PVs) are double-stranded DNA viruses ubiquitously present in mammals and are a suitable target for rigorous statistical tests of potential virus-host codivergence. We analyze the evolutionary dynamics of PV diversification by comparing robust phylogenies of PVs and their respective hosts using different statistical approaches to assess topological and branch-length congruence. Mammalian PVs segregated into four diverse major clades that overlapped to varying degrees in terms of their mammalian host lineages. The hypothesis that PVs and hosts evolved independently was globally rejected (P = 0.0001), although only 90 of 207 virus-host associations (43%) were significant in individual tests. Virus-host codivergence accounted roughly for one-third of the evolutionary events required to reconcile PV-host evolutionary histories. When virus-host associations were analyzed locally within each of the four viral clades, numerous independent topological congruencies were identified that were incompatible with respect to the global trees. These results support an evolutionary scenario in which early PV radiation was followed by independent codivergence between viruses within each of the major clades and their hosts. Moreover, heterogeneous groups of closely related PVs infecting non-related hosts suggest several interspecies transmission events. Our results argue thus for the importance of alternative events in PV evolution, in contrast to the prevailing opinion that these viruses show a high degree of host specificity and codivergence.