The isolation of populations in the Iberian, Italian and Balkan peninsulas during the ice ages define four main paradigms that explain much of the known distribution of intraspecific genetic diversity in Europe. In this study we investigated the phylogeography of a wide-spread bat species, the bent-winged bat, Miniopterus schreibersii around the Mediterranean basin and in the Caucasus. Environmental niche modeling (ENM) analysis was applied to predict both the current distribution of the species and its distribution during the last glacial maximum (LGM). The combination of genetics and ENM results suggest that the populations of M. schreibersii in Europe, the Caucasus and Anatolia went extinct during the LGM, and the refugium for the species was a relatively small area to the east of the Levantine Sea, corresponding to the Mediterranean coasts of present-day Syria, Lebanon, Israel, and northeastern and northwestern Egypt. Subsequently the species first repopulated Anatolia, diversified there, and afterwards expanded into the Caucasus, continental Europe and North Africa after the end of the LGM. The fossil record in Iberia and the ENM results indicate continuous presence of Miniopterus in this peninsula that most probably was related to the Maghrebian lineage during the LGM, which did not persist afterwards. Using our results combined with similar findings in previous studies, we propose a new paradigm explaining the general distribution of genetic diversity in Europe involving the recolonization of the continent, with the main contribution from refugial populations in Anatolia and the Middle East. The study shows how genetics and ENM approaches can complement each other in providing a more detailed picture of intraspecific evolution.