Termites digest wood and other lignocellulosic substrates with the help of their intestinal microbiota. While the functions of the symbionts in the digestive process are slowly emerging, the origin of the bacteria colonizing the hindgut bioreactor is entirely unknown. Recently, our group discovered numerous representatives of bacterial lineages specific to termite guts in a closely related omnivorous cockroach, but it remains unclear whether they derive from the microbiota of a common ancestor or were independently selected by the gut environment. Here, we studied the bacterial gut microbiota in 34 species of termites and cockroaches using pyrotag analysis of the 16S rRNA genes. Although the community structures differed greatly between the major host groups, with dramatic changes in the relative abundances of particular bacterial taxa, we found that the majority of sequence reads belonged to bacterial lineages that were shared among most host species. When mapped onto the host tree, the changes in community structure coincided with major events in termite evolution, such as acquisition and loss of cellulolytic protists and the ensuing dietary diversification. UniFrac analysis of the core microbiota of termites and cockroaches and construction of phylogenetic tree of individual genus level lineages revealed a general host signal, whereas the branching order often did not match the detailed phylogeny of the host. It remains unclear whether the lineages in question have been associated with the ancestral cockroach since the early Cretaceous (cospeciation) or are diet-specific lineages that were independently acquired from the environment (host selection).