Coevolutionary theory predicts that the distribution of obligately symbiotic organisms will be determined by the dispersal ability and ecological range of both partners. We examined this prediction for lichen-forming fungi that form obligate symbioses with cyanobacteria. We compared genotypes of both partners of 250 lichens collected at multiple spatial scales in British Columbia, Canada. Multilocus sequence data collected from a subset of 128 of the specimens were used to determine the degree of recombination within the cyanobacterial populations. We found that six distinct clusters of cyanobacterial genotypes are distributed throughout the known global phylogeny of the genus Nostoc, and that each appears to be evolving clonally. Fungal specialization is high, with each species associating with either one or two of the cyanobacterial clusters, while cyanobacterial specialization varies, with clusters associating with between one and 12 different fungal species. Specialization also varies geographically, with some combinations restricted to a single site despite the availability of both partners elsewhere. Photobiont association patterns are determined by a combination of genetically based specificity, spatial population structure, and ecological factors and cannot be easily predicted by photobiont dispersal syndromes.