We took advantage of a five-decade ‘chronosequence’ of host-microbiome evolution to examine changes in the gut microbiome as wild populations evolve. In an iconic example of rapid evolution in the wild, Trinidadian guppies have displayed parallel phenotypic convergence when translocated six times from high predation (HP) to low predation (LP) environments, but changes in microbiome are unknown. We find microbiomes of fish translocated 5-6 years ago were already more similar to LP native populations than HP sources, and attribute this to both environmental and host-morphological changes. While diet was a minor driver of microbiome structure, we suggest a nutritional role for the gut microbiome in guppy evolution whereby nitrogen-fixing bacteria supplement the low-nutrient diet in LP environments. We show that environment and rapid phenotypic shifts in gut traits interact to control microbiome assembly, and suggest the gut microbiome plays an important but not necessarily consistent role in rapid host evolution.