Heterocystous cyanobacteria form symbiotic associations with a wide range of plant and fungal hosts. We used a molecular phylogenetic approach to investigate the degree of host specialization of cyanobacteria associated with four closely related species of the lichenized fungus Peltigera, and to compare these strains with other symbiotic cyanobacteria. We conducted phylogenetic analyses on 16S, rbcLX, and trnL sequences from cyanobacteria associated with multiple specimens of each lichen species and from symbionts of other fungi and plants, as well as from free-living strains of Nostoc and related genera of cyanobacteria. The genus Nostoc comprises two divergent lineages, but symbiotic strains occur primarily within a single monophyletic lineage that also includes free-living representatives. Cyanobacteria from the same lichen species were often more closely related to strains from other species or to plant symbionts or free-living strains than to each other. These results indicate that host specialization is low for the genus Nostoc, and suggest that opportunities for coevolution with its partners may be rare. © 2005 British Phycological Society.