INTRODUCTION: Diverse insects and other organisms are associated with microbial symbionts, which often significantly contribute to growth and survival of their hosts and/or drastically affect phenotypes of their hosts in a variety of ways. Sodalis glossinidius was first identified as a facultative bacterial symbiont of tsetse flies, and recent studies revealed that Sodalis-allied bacteria encompass diverse ecological niches ranging from free-living bacteria through facultative symbionts to obligate symbionts associated with a diverse array of insects. Despite potential ecological and evolutionary relevance of the Sodalis symbionts, their infection prevalence in natural insect populations has been poorly investigated. RESULTS: Here we surveyed diverse stinkbugs and allied terrestrial heteropteran bugs, which represented 17 families, 77 genera, 108 species, 310 populations and 960 individuals, for infection with the Sodalis symbionts. Diagnostic PCR detected relatively low infection frequencies of the Sodalis symbionts: 13.6% (14/103) of the species, 7.5% (22/295) of the populations, and 4.3% (35/822) of the individuals of the stinkbugs except for those belonging to the family Urostylididae. Among the urostylidid stinkbugs, strikingly, the Sodalis symbionts exhibited very high infection frequencies: 100% (5/5) of the species, 100% (15/15) of the populations, and 94.2% (130/138) of the individuals we examined. Molecular phylogenetic analysis based on bacterial 16S rRNA gene sequences revealed that all the symbionts were placed in the clade of Sodalis-allied bacteria while the symbiont phylogeny did not reflect the systematics of their stinkbug hosts. Notably, the Sodalis symbionts of the urostylidid stinkbugs were not clustered with the Sodalis symbionts of the other stinkbug groups on the phylogeny, suggesting their distinct evolutionary trajectories. CONCLUSIONS: The relatively low infection frequency and the overall host-symbiont phylogenetic incongruence suggest that the Sodalis symbionts are, in general, facultative symbiotic associates in the majority of the stinkbug groups. On the other hand, it is conceivable, although speculative, that the Sodalis symbionts may play some substantial biological roles for their host stinkbugs of the Urostylididae.