Social insects exhibit a high degree of intraspecific behavioral variation. Moreover, they often harbor specialized microbial communities in their gut. Recent studies suggest that these two characteristics of social insects are interlinked: insect behavioral phenotypes affect their gut microbiota composition, partly through exposure to different environments and diet, and in return, the gut microbiota has been shown to influence insect behavior. Here we discuss the bidirectional relationship existing between intraspecific variation in gut microbiota composition and behavioral phenotypes in social insects.