Papillomaviruses cause persistent infections in skin and mucosal membranes and, in at least one species, are also be able to infect a tissue of mesenchymal origin. Infections may either be subclinical or induce proliferative lesions. Of the known papillomaviruses, the majority that have been characterized are from humans and other mammals. Currently, only fifteen complete bird and reptile papillomavirus genomes have been described, and they have been found in birds (n = 11), turtles (n = 2), and snakes (n = 2). Using next-generation sequencing technologies and virus-specific PCR, we have identified two novel papillomavirus genomes, Hemidactylus frenatus Papillomavirus 1 and 2 (HfrePV1, HfrePV2), in the widely distributed and highly invasive Asian house gecko (H.frenatus) and mute gecko (Gehyra mutilata) on Christmas Island and Cocos (Keeling) Islands. HfrePV1 was also detected in critically endangered Lister’s geckos (Lepidodactylus listeri) in their captive breeding colony on Christmas Island. Tissue-containing virus included epidermis, oral mucosa, and liver (HfrePV1) and epidermis, liver, and colon (HfrePV2). Concurrent infections were found in both H.frenatus and G.mutilata. Invasive mourning geckos (Lepidodactylus lugubris) (n = 4), Sri Lankan house geckos (Hemidactylus parvimaculatus) (n = 3), flat-tailed house geckos (Hemidactylus platyurus) (n = 4) from the Cocos Islands, and blue-tailed skinks (Cryptoblepharus egeriae) (n = 10) from Christmas Island were also screened but were not found to be infected. The novel HfrePV1 and HfrePV2 genomes were 7,378 bp and 7,380 bp in length, respectively, and each contained the early (E1, E2, and E7), and late (L1 and L2) open-reading frames. Phylogenetic analysis of the concatenated E1, E2, and L1 proteins from both papillomaviruses revealed that they clustered with, but were basal to, the Sauropsida clade containing bird and reptile viruses. This study sheds light on the evolution of papillomaviruses and the distribution of pathogens in a highly invasive species impacting endangered populations of geckos.