In addition to harbouring intestinal symbionts, some animal species also possess intracellular symbiotic microbes. The relative contributions of gut-resident and intracellular symbionts to host metabolism, and how they coevolve are not well understood. Cockroaches and the termite Mastotermes darwiniensis present a unique opportunity to examine the evolution of spatially separated symbionts, as they harbour gut symbionts and the intracellular symbiont Blattabacterium cuenoti. The genomes of B. cuenoti from M. darwiniensis and the social wood-feeding cockroach Cryptocercus punctulatus are each missing most of the pathways for the synthesis of essential amino acids found in the genomes of relatives from non-wood-feeding hosts. Hypotheses to explain this pathway degradation include: (i) feeding on microbes present in rotting wood by ancestral hosts; (ii) the evolution of high-fidelity transfer of gut microbes via social behaviour. To test these hypotheses, we sequenced the B. cuenoti genome of a third wood-feeding species, the phylogenetically distant and non-social Panesthia angustipennis. We show that host wood-feeding does not necessarily lead to degradation of essential amino acid synthesis pathways in B. cuenoti, and argue that ancestral high-fidelity transfer of gut microbes best explains their loss in strains from M. darwiniensis and C. punctulatus.