Patterns of specificity among symbiotic partners are key to a comprehensive understanding of the evolution of symbiotic systems. Specificity of mutualistic partners, within a widespread monophyletic group for which all species are sampled has rarely been explored. Here we assess the level of specificity between the cosmopolitan lichen-forming fungus (mycobiont) from the genus Peltigera, section Polydactylon, and its cyanobacterial partner Nostoc (cyanobiont). The mycobiont and cyanobiont phylogenies are inferred from five nuclear loci and the rbcLX region, respectively. These sequences were obtained from 206 lichen thalli, representing ca. 40 closely related Peltigera species sampled worldwide, doubling the number of known species in this group. We found a broad spectrum of specificity for both partners ranging from strict specialists to generalists. Overall, mycobionts are more specialized than cyanobionts by associating mostly with one or a few Nostoc phylogroups, whereas most cyanobionts associate frequently with several Peltigera species. Specialist mycobionts are older than generalists, supporting the hypothesis that specialization of mycobionts to one or few cyanobionts, is favored through time in geographic areas where species have been established for long periods of time. The relatively recent colonization of a new geographic area (Central and South America) by members of section Polydactylon is associated with a switch to a generalist pattern of association and an increased diversification rate by the fungal partner, suggesting that switches to generalism are rare events that are advantageous in new environments. We detected higher genetic diversity in generalist mycobionts. We also found that Peltigera species specialized on a single Nostoc phylogroup have narrower geographical distributions compared to generalist species.