In lichen symbiosis, fungal and algal partners form close associations, often co-dispersed by vegetative propagules. Due to the particular interdependence, processes such as colonization, dispersal or genetic drift are expected to result in congruent patterns of genetic structure in the symbionts. To study the population structure of an obligate symbiotic system in Europe, we genotyped the fungal and algal symbionts of the epiphytic lichen Lobaria pulmonaria at eight and seven microsatellite loci, respectively, and analyzed about 4300 L. pulmonaria thalli from 142 populations from the species' European distribution range. Based on a centroid approach, which localizes centers of genetic differentiation with a high frequency of geographically restricted alleles, we identified the South Italy-Balkan region as the primary glacial refugial area of the lichen symbiosis. Procrustean rotation analysis and a distance congruence test between the fungal and algal population graphs indicated general concordance between the phylogeographies of the symbionts. The incongruent patterns found in areas of post-glacial recolonization may show the presence of an additional refugial area for the fungal symbiont, and the impact that horizontal photobiont transmission and different mutation rates of the symbionts have on their genotypic associations at a continental scale.