Bats are natural hosts of a wide variety of viruses, including adenoviruses. European bats are known to carry mastadenoviruses categorized as species B (widespread in European Vespertilionidae bats) and whose taxonomy has not been clarified. We examined fecal samples from Vespertilionidae bats (five species) captured in central Russia and found that 2/12 (16%) were positive for mastadenoviruses. The partial genome of the mastadenovirus was assembled from Pipistrellus nathusii, representing the bat adenovirus species B. The complete genome (37,915 nt) of a novel mastadenovirus was assembled from Nyctalus noctula and named BatAdV/MOW15-Nn19/Quixote. Comparative studies showed significant divergence of the Quixote genome sequence from European bat mastadenoviruses, while the only known virus showing low similarity was the isolate WA3301 from an Australian bat, and together they formed a subclade that separated from other BatAdVs. Phylogenetic and comparative analysis of the protein-coding genes provided evidence that Quixote is related to a novel species within the genus Mastadenovirus, provisionally named “K” (as the next available letter for the species). Phylogenetic analyses revealed that some earlier viruses from Western European bats, for which only partial DNA polymerase genes are known, are most likely members of the tentatively named species “K”. Thus, at least two species of mastadenovirus are circulating in bats throughout Europe, from western to eastern areas.