The crucial role of the gut microbiota for the ecology and evolution of their hosts is becoming increasingly appreciated. Yet, we still lack knowledge of how the interaction between hosts and their microbial hitchhikers affects the hosts’ adaptation to new niches and to what extent compositional and functional changes of the gut microbiota can be predicted. Here, we study the relative contribution of host ecology and morphology as well as abiotic and biotic characteristics of the environment in driving patterns of gut microbiota variation (based on 16S rRNA gene sequencing) within and among populations. Further, we ask whether the dietary niche width of host populations (i.e., generalist vs. specialist) is associated with variation in the gut microbiota, which might influence host trophic specialization and adaptation. We address this question in a comparative framework across eight natural populations of threespine stickleback from British Columbia, Canada, that show substantial variation in diet along the benthic-limnetic axis. The results obtained in the course of this study allow us to determine the factors, which are key to determining predictability in gut microbiota community assembly. Quantifying the magnitude of predictability is crucial for understanding how a host, its gut microbiota and the environment interact during the adaptation to different ecological niches.