Cryptocercus punctulatus and Parasphaeria boleiriana are two distantly related xylophagous and subsocial cockroaches. Cryptocercus is related to termites. Xylophagous cockroaches and termites are excellent model organisms for studying the symbiotic relationship between the insect and their microbiota. In this study, high-throughput 454 pyrosequencing of 16S rRNA was used to investigate the diversity of metagenomic gut communities of C. punctulatus and P. boleiriana, and thereby to identify possible shifts in symbiont allegiances during cockroaches evolution. Our results revealed that the hindgut prokaryotic communities of both xylophagous cockroaches are dominated by members of four Bacteria phyla: Bacteroidetes, Firmicutes, Proteobacteria, and Actinobacteria. Other identified phyla were Spirochaetes, Planctomycetes, candidatus Saccharibacteria (formerly TM7), and Acidobacteria, each of which represented 1-2% of the total population detected. Community similarity based on phylogenetic relatedness by unweighted UniFrac analyses indicated that the composition of the bacterial community in the two species was significantly different (P < 0.05). Phylogenetic analysis based on the characterized clusters of Bacteroidetes, Spirochaetes, and Deltaproteobacteria showed that many OTUs present in both cockroach species clustered with sequences previously described in termites and other cockroaches, but not with those from other animals or environments. These results suggest that, during their evolution, those cockroaches conserved several bacterial communities from the microbiota of a common ancestor. The ecological stability of those microbial communities may imply the important functional role for the survival of the host of providing nutrients in appropriate quantities and balance.