Social interactions can facilitate transmission of microbes between individuals, reducing variation in gut communities within social groups. Thus, the evolution of social behaviors and symbiont community composition have the potential to be tightly linked. We explored this connection by characterizing the diversity of bacteria associated with both eusocial and solitary bee species within the behaviorally variable family Halictidae using 16S amplicon sequencing. Contrary to expectations, we found few differences in bacterial abundance or variation between social forms; most halictid species appear to share similar gut bacterial communities. However, several strains of Sodalis, a genus described as a symbiont in a variety of insects but yet to be characterized in bees, differ in abundance between eusocial and solitary bees. Phylogenetic reconstructions based on whole-genome alignments indicate that Sodalis has independently colonized halictids at least three times. These strains appear to be mutually exclusive within individual bees, although they are not host-species-specific and no signatures of vertical transmission were observed, suggesting that Sodalis strains compete for access to hosts. The symbiosis between halictids and Sodalis therefore appears to be in its early stages.