Papillomaviruses (PV) are a diverse group of species-specific, small DNA viruses, etiologically linked with various benign and malignant neoplasms of cutaneous and mucousal epithelia. The aim of our study was to completely characterize at least one novel PV type, naturally infecting Japanese macaques (Macaca fuscata), and to determine its etiological association with the development of the original neoplastic lesion. The molecular and phylogenetic analyses were performed on complete genome sequences of Macaca fuscata PV type 1 (MfuPV1) and MfuPV2, which have been completely sequenced in a sample of an oral malignant neoplasm and benign anogenital neoplasm of a Japanese macaque, respectively. The molecular analyses revealed that both viral genomes encode characteristic proteins with conserved functional domains and have a non-coding genomic region with regulatory sequences, which enable viruses to complete their life cycles and infect novel host cells. While MfuPV1 together with PVs identified in anogenital mucosa of long-tailed and rhesus macaques clusters within the Alphapapillomavirus species 12, MfuPV2 is most likely a representative of the novel viral species within the genus Alphapapillomavirus. Based on the relatively high viral loads of MfuPV1 and MfuPV2, we believe that both novel PV types could be etiologically linked with original neoplastic lesions.