Because the number of fungal species (mycobionts) exceeds the number of algae and cyanobacteria (photobionts) found in lichens by more than two orders of magnitude, reciprocal one-to-one specificity between one fungal species and one photobiont across their entire distribution is not expected in this symbiotic system, and has not previously been observed. The specificity of the cyanobacterium Nostoc found in lichens was evaluated at a broad geographical scale within one of the main families of lichen-forming fungi (Collemataceae) that associate exclusively with this photobiont. A phylogenetic study was conducted using rbcLXS sequences from Nostoc sampled from 79 thalli (representing 24 species within the Collemataceae), and 163 Nostoc sequences gathered from GenBank. Although most of the lichen-forming fungal species belonging to the Collemataceae exhibited the expected generalist pattern of association with multiple distinct lineages of Nostoc, five independent cases of one-to-one reciprocal specificity at the species level, including two that span intercontinental distributions, were discovered. Each of the five distinct monophyletic Nostoc groups, associated with these five highly specific mycobiont species, represent independent transitions from a generalist state during the evolution of both partners, which might be explained by transitions to asexual fungal reproduction, involving vertical photobiont transmission, and narrowing of ecological niches.