Mutualistic coevolution can be mediated by vertical transmission of symbionts between host generations. Termites host complex gut bacterial communities with evolutionary histories indicative of mixed-mode transmission. Here, we document that vertical transmission of gut bacterial strains is congruent across parent to offspring colonies in four pedigrees of the fungus-farming termite Macrotermes natalensis. We show that 44% of the offspring colony microbiome, including more than 80 bacterial genera and pedigree-specific strains, are consistently inherited. We go on to demonstrate that this is achieved because colony-founding reproductives are selectively enriched with a set of non-random, environmentally sensitive and termite-specific gut microbes from their colonies of origin. These symbionts transfer to offspring colony workers with high fidelity, after which priority effects appear to influence the composition of the establishing microbiome. Termite reproductives thus secure transmission of complex communities of specific, co-evolved microbes that are critical to their offspring colonies. Extensive yet imperfect inheritance implies that the maturing colony benefits from acquiring environmental microbes to complement combinations of termite, fungus and vertically transmitted microbes; a mode of transmission that is emerging as a prevailing strategy for hosts to assemble complex adaptive microbiomes.