Microbiomes play a critical role in promoting a range of host functions. Microbiome function, in turn, is dependent on its community composition. Yet, how microbiome taxa are assembled from their regional species pool remains unclear. Many possible drivers have been hypothesized, including deterministic processes of competition, stochastic processes of colonization and migration, and physiological 'host-effect' habitat filters. The contribution of each to assembly in nascent or perturbed microbiomes is important for understanding host-microbe interactions and host health. In this study, we characterized the bacterial communities in a euryhaline fish and the surrounding tank water during salinity acclimation. To assess the relative influence of stochastic versus deterministic processes in fish microbiome assembly, we manipulated the bacterial species pool around each fish by changing the salinity of aquarium water. Our results show a complete and repeatable turnover of dominant bacterial taxa in the microbiomes from individuals of the same species after acclimation to the same salinity. We show that changes in fish microbiomes are not correlated with corresponding changes to abundant taxa in tank water communities and that the dominant taxa in fish microbiomes are rare in the aquatic surroundings, and vice versa. Our results suggest that bacterial taxa best able to compete within the unique host environment at a given salinity appropriate the most niche space, independent of their relative abundance in tank water communities. In this experiment, deterministic processes appear to drive fish microbiome assembly, with little evidence for stochastic colonization.