Background: There is a growing concern that global climate change will affect the potential for pathogen transmission by insect species that are vectors of human diseases. One of these species is the former European malaria vector, Anopheles atroparvus. Levels of population differentiation of An. atroparvus from southern Europe were characterized as a first attempt to elucidate patterns of population structure of this former malaria vector. Results are discussed in light of a hypothetical situation of re-establishment of malaria transmission. Methods: Genetic and phenotypic variation was analysed in nine mosquito samples collected from five European countries, using eight microsatellite loci and geometric morphometrics on 21 wing landmarks. Results: Levels of genetic diversity were comparable to those reported for tropical malaria vectors. Low levels of genetic (0.004 <FST<0.086) and phenotypic differentiation were detected among An. atroparvus populations spanning over 3,000 km distance. Genetic differentiation (0.202 <F ST<0.299) was higher between the sibling species An. atroparvus and Anopheles maculipennis s.s. Differentiation between sibling species was not so evident at the phenotype level. Conclusions: Levels of population differentiation within An. atroparvus were low and not correlated with geographic distance or with putative physical barriers to gene flow (Alps and Pyrenées). While these results may suggest considerable levels of gene flow, other explanations such as the effect of historical population perturbations can also be hypothesized.