The large distributional areas and ecological niches of many lichenized fungi may in part be due to the plasticity in interactions between the fungus (mycobiont) and its algal or cyanobacterial partners (photobionts). On the one hand, broad-scale phylogenetic analyses show that partner compatibility in lichens is rather constrained and shaped by reciprocal selection pressures and codiversification independent of ecological drivers. On the other hand, sub-species-level associations among lichen symbionts appear to be environmentally structured rather than phylogenetically constrained. In particular, switching between photobiont ecotypes with distinct environmental preferences has been hypothesized as an adaptive strategy for lichen-forming fungi to broaden their ecological niche. The extent and direction of photobiont-mediated range expansions in lichens, however, have not been examined comprehensively at a broad geographic scale. Here we investigate the population genetic structure of Lasallia pustulata symbionts at sub-species-level resolution across the mycobiont's Europe-wide range, using fungal MCM7 and algal ITS rDNA sequence markers. We show that variance in occurrence probabilities in the geographic distribution of genetic diversity in mycobiont-photobiont interactions is closely related to changes in climatic niches. Quantification of niche extent and overlap based on species distribution modeling and construction of Hutchinsonian climatic hypervolumes revealed that combinations of fungal-algal interactions change at the sub-species level along latitudinal temperature gradients and in Mediterranean climate zones. Our study provides evidence for symbiont-mediated niche expansion in lichens. We discuss our results in the light of symbiont polymorphism and partner switching as potential mechanisms of environmental adaptation and niche evolution in mutualisms.