We have estimated phylogenies of fungus-growing termites and their associated mutualistic fungi of the genus Termitomyces using Bayesian analyses of DNA sequences. Our study shows that the symbiosis has a single African origin and that secondary domestication of other fungi or reversal of mutualistic fungi to a free-living state has not occurred. Host switching has been frequent, especially at the lower taxonomic levels, and nests of single termite species can have different symbionts. Data are consistent with horizontal transmission of fungal symbionts in both the ancestral state of the mutualism and most of the extant taxa. Clonal vertical transmission of fungi, previously shown to be common in the genus Microtermes (via females) and in the species Macrotermes bellicosus (via males) [Johnson, R. A., Thomas, R. J., Wood, T. G. & Swift, M. J. (1981) J. Nat. Hist. 15, 751–756], is derived with two independent origins. Despite repeated host switching, statistical tests taking phylogenetic uncertainty into account show a significant congruence between the termite and fungal phylogenies, because mutualistic interactions at higher taxonomic levels show considerable specificity. We identify common characteristics of fungus-farming evolution in termites and ants, which apply despite the major differences between these two insect agricultural systems. We hypothesize that biparental colony founding may have constrained the evolution of vertical symbiont transmission in termites but not in ants where males die after mating.