Although understood in many vertebrate systems, the natural diversity of host-associated microbiota has been little studied in teleosts. For migratory fishes, successful exploitation of multiple habitats may affect and be affected by the composition of the intestinal microbiome. We collected 96 Salmo salar from across the Atlantic encompassing both freshwater and marine phases. Dramatic differences between environmental and gut bacterial communities were observed. Furthermore, community composition was not significantly impacted by geography. Instead life-cycle stage strongly defined both the diversity and identity of microbial assemblages in the gut, with evidence for community destabilisation in migratory phases. Mycoplasmataceae phylotypes were abundantly recovered in all life-cycle stages. Patterns of Mycoplasmataceae phylotype recruitment to the intestinal microbial community among sites and life-cycle stages support a dual role for deterministic and stochastic processes in defining the composition of the S. salar gut microbiome.