Hemipteran insects are well-known in their ability to establish symbiotic relationships with bacteria. Among them, heteropteran insects present an array of symbiotic systems, ranging from the most common gut crypt symbiosis to the more restricted bacteriome-associated endosymbiosis, which have only been detected in members of the superfamily Lygaeoidea and the family Cimicidae so far. Genomic data of heteropteran endosymbionts are scarce and have merely been analyzed from the Wolbachia endosymbiont in bed bug and a few gut crypt-associated symbionts in pentatomoid bugs. In this study, we present the first detailed genomic analysis of a bacteriome-associated endosymbiont of a phytophagous heteropteran, present in the seed bug Henestaris halophilus (Hemiptera: Heteroptera: Lygaeoidea). Using phylogenomics and genomics approaches, we have assigned the newly characterized endosymbiont to the Sodalis genus, named as Candidatus Sodalis baculum sp. nov. strain kilmister. In addition, our findings support the reunification of the Sodalis genus, currently divided into six different genera. We have also conducted comparative analyses between 15 Sodalis species that present different genome sizes and symbiotic relationships. These analyses suggest that Ca. Sodalis baculum is a mutualistic endosymbiont capable of supplying the amino acids tyrosine, lysine, and some cofactors to its host. It has a small genome with pseudogenes but no mobile elements, which indicates middle-stage reductive evolution. Most of the genes in Ca. Sodalis baculum are likely to be evolving under purifying selection with several signals pointing to the retention of the lysine/tyrosine biosynthetic pathways compared with other Sodalis.