Animals are home to diverse bacterial communities that can affect their hosts' physiology, metabolism, and susceptibility to disease. Here we highlight recent research that reveals surprising and important connections between an individual's microbiome and its social behavior. We focus on two recent discoveries: (i) that social interactions can affect the taxonomic and genic composition of animal microbiomes, with consequences for microbiome function and potentially host fitness, and (ii) that microbiomes can affect host social behavior by producing chemical signals used in social communication and by directly influencing host nervous systems. Investigating the reciprocal relationships between host behavior and the microbiome thus promises to shed new light on both the evolution of host social behavior and microbial transmission strategies.