Lichens are intimate and long-term symbioses of algae and fungi. Such intimate associations are often hypothesized to have undergone long periods of symbiotic interdependence and coevolution. However, coevolution has not been rigorously tested for lichen associations. In the present study we compared the nuclear internal transcribed spacer (ITS) phylogenies of algal and fungal partners from 33 natural lichen associations to test two aspects of coevolution, cospeciation and parallel cladogenesis. Since statistically significant incongruence between symbiont phylogenies rejected parallel cladogenesis and minimized cospeciation events, we conclude that switching of highly selected algal genotypes occurs repeatedly among these symbiotic lichen associations.