Past climate change is known to have strongly impacted current patterns of genetic variation of animals and plants in Europe. However, ecological factors also have the potential to influence demographic history and thus patterns of genetic variation. In this study, we investigated the impact of past climate, and also the potential impact of host plant species abundance, on intraspecific genetic variation in three codistributed and related specialized solitary bees of the genus Melitta with very similar life history traits and dispersal capacities. We sequenced five independent loci in samples collected from the three species. Our analyses revealed that the species associated with the most abundant host plant species (Melitta leporina) displays unusually high genetic variation, to an extent that is seldom reported in phylogeographic studies of animals and plants. This suggests a potential role of food resource abundance in determining current patterns of genetic variation in specialized herbivorous insects. Patterns of genetic variation in the two other species indicated lower overall levels of diversity, and that M.nigricans could have experienced a recent range expansion. Ecological niche modelling of the three Melitta species and their main host plant species suggested a strong reduction in range size during the last glacial maximum. Comparing observed sequence data with data simulated using spatially explicit models of coalescence suggests that M.leporina recovered a range and population size close to their current levels at the end of the last glaciation, and confirms recent range expansion as the most likely scenario for M.nigricans. Overall, this study illustrates that both demographic history and ecological factors may have contributed to shape current phylogeographic patterns.