For a better understanding of the complex coevolutionary processes between hosts and parasites, accurate identification of the actors involved in the interaction is of fundamental importance. Blood parasites of the Order Haemosporidia, responsible for malaria, have become the focus of a broad range of studies in evolutionary biology. Interestingly, molecular-based studies on avian malaria have revealed much higher species diversity than previously inferred with morphology. Meanwhile, studies on bat haemosporidian have been largely neglected. In Europe, only one genus (Polychromophilus) and two species have been morphologically described. To evaluate the presence of potential cryptic species and parasite prevalence, we undertook a molecular characterization of Polychromophilus in temperate zone bats. We used a nested-PCR approach on the cytochrome b mitochondrial gene to detect the presence of parasites in 237 bats belonging to four different species and in the dipteran bat fly Nycteribia kolenatii, previously described as being the vector of Polychromophilus. Polychromophilus murinus was found in the four bat species and in the insect vector with prevalence ranging from 4% for Myotis myotis to 51% for M. daubentoni. By sequencing 682 bp, we then investigated the phylogenetic relationships of Polychromophilus to other published malarial lineages. Seven haplotypes were found, all very closely related, suggesting the presence of a single species in our samples. These haplotypes formed a well-defined clade together with Haemosporidia of tropical bats, revealing a worldwide distribution of this parasite mostly neglected by malarial studies since the 1980s.