All colonies of the fungus-growing termite Macrotermes natalensis studied so far are associated with a single genetically variable lineage of Termitomyces symbionts. Such limited genetic variation of symbionts and the absence of sexual fruiting bodies (mushrooms) on M. natalensis mounds would be compatible with clonal vertical transmission, as is known to occur in Macrotermes bellicosus. We investigated this hypothesis by analysing DNA sequence polymorphisms as codominant SNP markers of four single-copy gene fragments of Termitomyces isolates from 31 colonies of M. natalensis. A signature of free recombination was found, indicative of frequent sexual horizontal transmission. First, all 31 strains had unique multilocus genotypes. Second, SNP markers (n = 55) were largely in Hardy-Weinberg equilibrium (90.9%) and almost all possible pairs of SNPs between genetically unlinked loci were in linkage equilibrium (96.7%). Finally, extensive intragenic recombination was found, especially in the EF1a fragment. Substantial genetic variation and a freely recombining population structure can only be explained by frequent horizontal and sexual transmission of Termitomyces. The apparent variation in symbiont transmission mode among Macrotermes species implies that vertical symbiont transmission can evolve rapidly. The unexpected finding of horizontal transmission makes the apparent absence of Termitomyces mushrooms on M. natalensis mounds puzzling. To our knowledge, this is the first detailed study of the genetic population structure of a single lineage of Termitomyces.