The Lyme borreliosis (LB) group of spirochaetes currently comprises 18 named species that vary in their geographic distribution, host specificity and ability to cause disease in humans. In Europe three species are most abundant, Borrelia afzelii, Borrelia garinii and Borrelia valaisiana but only two of these (B. garinii and B. afzelii) are regularly found in Asia as well. A recently published study has shown that Borrelia species associated with birds, such as B. garinii, showed limited geographic structuring between European countries while, the rodent associated species, B. afzelii, showed extensive spatial structuring in Europe. Here, we use multilocus sequence analysis to show that when the wider, inter-continental, distribution is considered, there is evidence of spatial structuring even in the bird-associated species B. garinii. Furthermore, our investigations into historical LB populations provided evidence for range expansions of B. garinii and B. afzelii populations in Europe in the distant past. We propose that the expansion of B. afzelii in Europe may be linked to rodent population expansions after the last glacial maximum.