An increasing number of studies are describing the diversity of lichen phycobionts, which is leading to a better understanding of how lichen communities are assembled at different taxonomic, evolutionary and geographical scales. The present study explores the identity and genetic diversity of the microalgal partners of Punctelia borreri and P. subrudecta, two tropical and temperate parmelioid lichen fungi that often grow in temperate and Mediterranean forest ecosystems in Europe. Based on a specimen sampling distributed in two climatically divergent regions in the Iberian Peninsula, we found that these mycobionts are associated with Trebouxia gelatinosa, whose identity was also confirmed by an ultrastructural study of the pyrenoid. The bipartite network analysis indicated that each Punctelia species was associated with a different set of low frequency T. gelatinosa infraspecific lineages, whereas the two most abundant phycobiont lineages were shared between both mycobionts. Based on the current sampling, these two algal lineages occur exclusively in one of the two studied regions, which might point towards climate-driven, fine-tuned fungal-algal interactions. Finally, we documented visible symptoms of injury on the thalli in areas likely to have been impacted by air pollution.