Lichens are an iconic example of symbiotic systems whose ecology is shaped by all symbionts' requirements. Previous studies suggest that fungal (mycobionts), as well as photosynthesizing (phycobionts or cyanobionts), partners have a specific range of acceptable symbionts that can be changed according to specific environmental conditions. This study aimed to investigate the effects of climatic conditions and mycobiont identity on phycobiont distribution within the lichen genera Stereocaulon, Cladonia, and Lepraria. The study area comprised the Canary Islands, Madeira, Sicily, and the Aeolian Islands, spanning a wide range of climatic conditions. Though these islands are known for unique and diverse fauna and flora, lichen phycobionts remained unstudied in most of the area. In total, we genetically analyzed more than 300 lichen samples. The phycobiont pool differed significantly from that of outside the studied area. Asterochloris mediterranea was identified as the most abundant phycobiont. However, its distribution was limited by climatic constraints. Other species of Asterochloris, Chloroidium, Vulcanochloris, and Myrmecia were also recovered as phycobionts. The selection of symbiotic partners from the local phycobiont pool was driven by mycobiont specificity (i.e., the taxonomic range of acceptable partners) as well as by environmental conditions. Interestingly, the major fungal species responded differently in their selection of algal symbionts along the environmental gradients. Funding: Charles University Science Foundation project GAUK (grant no. 570313) and Primus Research Programme of Charles University (grant no. SCI/13).