The processes of local adaptation and ecological speciation are often strongly shaped by biotic interactions such as competition and predation. One of the strongest lines of evidence that biotic interactions drive evolution comes from repeated divergence of lineages in association with repeated changes in the community of interacting species. Yet, relatively little is known about the repeatability of changes in gut microbial communities and their role in adaptation and divergence of host populations in nature. Here we utilize three cases of rapid, parallel adaptation and speciation in freshwater threespine stickleback to test for parallel changes in associated gut microbiomes. We find that features of the gut microbial communities have shifted repeatedly in the same direction in association with parallel divergence and speciation of stickleback hosts. These results suggest that changes to gut microbiomes can occur rapidly and predictably in conjunction with host evolution, and that host-microbe interactions might play an important role in host adaptation and diversification.