Elucidating the spatial dynamic and core constituents of the microbial communities found in association with arthropod hosts is of crucial importance for insects that may vector human or agricultural pathogens. The hematophagous Cimex lectularius (Hemiptera: Cimicidae), known as the human bed bug, has made a recent resurgence in North America, as well as worldwide, potentially owing to increased travel, climate change and resistance to insecticides. A comprehensive survey of the bed bug microbiome has not been performed to date, nor has an assessment of the spatial dynamics of its microbiome. Here we present a survey of internal and external bed bug microbial communities by amplifying the V4–V6 hypervariable region of the 16S rDNA gene region followed by 454 Titanium sequencing using 31 individuals from eight distinct collection locations obtained from residences in Cincinnati, OH. Across all samples, 97% of the microbial community is made up of two dominant OTUs, previously identified as the α-proteobacterium Wolbachia and an unnamed γ-proteobacterium from the Enterobacteriaceae. Microbial communities varied among host locations for measures of community diversity and exhibited structure according to collection location. This broad survey represents the most in-depth assessment, to date, of the microbes that associate with bed bugs.