Papillomaviruses (PVs) are a group of small DNA viruses that, with around 350 million years of evolution, acquired the capacity of infecting a broad range of vertebrates, including humans. To date, more than 300 PV types have been isolated. Viruses that have a long common evolutionary history with their host typically cause unapparent infections. However, in some Alpha-PV infections, lesions become apparent and may cause benign proliferative disorders or even malignant proliferative lesions of the cervix, vulva, vagina, anus, penis, and oropharynx. The incongruence observed between the topology of the phylogenetic tree of Alpha-PVs and that of their hosts suggests that virus-host codivergence is not the only evolutionary force that has driven the progression of PVs. The integration of the precursors of E5, E6, and E7 on the genome of the ancestral Alpha-PV was important and made the colonization of new niches and the emergence of carcinogenic types possible.