Papillomaviruses are a group of ubiquitous viruses that are often found in normal skin of humans, as well as a range of different vertebrates. In this study, swab samples collected from the healthy skin of 225 Australian animals from 54 species were analysed for the presence of papillomavirus DNA with the general skin papillomavirus primer pair FAP59/FAP64. A total of five putative and potential new animal papillomavirus types were identified from three different animal species. The papillomaviruses were detected in one monotreme and two marsupial species: three from koalas, and one each from an Eastern grey kangaroo and an echidna. The papillomavirus prevalence in the three species was 14% (10/72) in koalas, 20% (1/5) in echidnas and 4% (1/23) in Eastern grey kangaroos. Phylogenetic analysis was performed on the putative koala papillomavirus type that could be cloned and it appears in the phylogenetic tree as a novel putative papillomavirus; genus. The data extend the range of species infected by papillomaviruses to the most primitive mammals: the monotremes and the marsupials.