Reticulitermes flavipes (Isoptera: Rhinotermitidae) is a highly eusocial insect that thrives on recalcitrant lignocellulosic diets through nutritional symbioses with gut-dwelling prokaryotes and eukaryotes. In the R. flavipes hindgut, there are up to 12 eukaryotic protozoan symbionts; the number of prokaryotic symbionts has been estimated in the hundreds. Despite its biological relevance, this diverse community, to date, has been investigated only by culture- and cloning-dependent methods. Moreover, it is unclear how termite gut microbiomes respond to diet changes and what roles they play in lignocellulose digestion. This study utilized high-throughput 454 pyrosequencing of 16S V5-V6 amplicons to sample the hindgut lumen prokaryotic microbiota of R. flavipes and to examine compositional changes in response to lignin-rich and lignin-poor cellulose diets after a 7-day feeding period. Of the ~475 000 high-quality reads that were obtained, 99.9% were annotated as bacteria and 0.11% as archaea. Major bacterial phyla included Spirochaetes (24.9%), Elusimicrobia (19.8%), Firmicutes (17.8%), Bacteroidetes (14.1%), Proteobacteria (11.4%), Fibrobacteres (5.8%), Verrucomicrobia (2.0%), Actinobacteria (1.4%) and Tenericutes (1.3%). The R. flavipes hindgut lumen prokaryotic microbiota was found to contain over 4761 species-level phylotypes. However, diet-dependent shifts were not statistically significant or uniform across colonies, suggesting significant environmental and/or host genetic impacts on colony-level microbiome composition. These results provide insights into termite gut microbiome diversity and suggest that (i) the prokaryotic gut microbiota is much more complex than previously estimated, and (ii) environment, founding reproductive pair effects and/or host genetics influence microbiome composition.