Diverse phytophagous heteropteran insects, commonly known as stinkbugs, are associated with specific gut symbiotic bacteria, which have been found in midgut cryptic spaces. Recent studies have revealed that members of the stinkbug families Coreidae and Alydidae of the superfamily Coreoidea are consistently associated with a specific group of the betaproteobacterial genus Burkholderia, called the "stinkbug-associated beneficial and environmental (SBE)" group, and horizontally acquire specific symbionts from the environment every generation. However, the symbiotic system of another coreoid family, Stenocephalidae remains undetermined. We herein investigated four species of the stenocephalid genus Dicranocephalus. Examinations via fluorescence in situ hybridization (FISH) and transmission electron microscopy (TEM) revealed the typical arrangement and ultrastructures of midgut crypts and gut symbionts. Cloning and molecular phylogenetic analyses of bacterial genes showed that the midgut crypts of all species are colonized by Burkholderia strains, which were further assigned to different subgroups of the genus Burkholderia. In addition to the SBE-group Burkholderia, a number of stenocephalid symbionts belonged to a novel clade containing B. sordidicola and B. udeis, suggesting a specific symbiont clade for the Stenocephalidae. The symbiotic systems of stenocephalid bugs may provide a unique opportunity to study the ongoing evolution of symbiont associations in the stinkbug-Burkholderia interaction.