Populations of gastrointestinal microbiota depend on their hosts’ genetic, nutritional, and environmental factors, yet knowledge about how ecological processes contribute to the variation within and among host-associated microbial communities remains limited. Microbes present in aquatic habitats have a higher impact on living animals than is the case with terrestrial ones. Fish intestine comprises both indigenous microbiota and allochthonous ones constantly replenished via the ingestion of the surrounding waters. Such ever-changing heterogeneous conditions creates multiple niches allowing prokaryotes with diverse functional traits and niche preferences to coexist within the fish intestinal tract. We analyzed the microbial community composition of 193 fish intestinal content and intestinal mucosa samples from nine different sampling sites, together with 18 corresponding environmental ones. Our fish collection taxonomically represented 20 orders, 32 families and 41 species originating from different salinity habitats. Overall, fish intestinal microbiomes displayed highly dynamic composition, enriched in Proteobacteria, Firmicutes, Bacteroidota and Fusobacteriota, and was distinct from environmental bacterioplankton communities. Fish intestinal mucosa was associated with a stable and diverse microbiota which were divergent from intestinal content. Some prokaryotic taxa colonizing fish intestinal mucosa were shared among hosts diverged in phylogeny and adapted to different salinity. These shared indigenous prokaryotic symbionts might originate from a common ancestor, or from widely dispersed lineages that colonized distinct hosts subsequently. Comparisons among host individuals, taxonomic categories, salinity gradients and other influential factors demonstrated that hosts individual characteristics and environmental conditions interactively shape the gut microbiome of fish, and microbiome composition could be highly host species specific. Linear discriminant analysis effect size and random forest classification identified taxa that most likely explained differences in fish intestinal microbiome along salinity gradients. Phylogenetic comparison of these taxa to existent microbial database revealed putative environmental generalists and host-associated specialists. We also analyzed 159 metagenomes generated from the same samples as the amplicon datasets. High quality genomes were recovered from a wide range of taxonomy groups, and exhibited host phylogeny and ecology specific characteristics. Our findings emphasized the role of salinity and inter-individual variability in shaping fish intestinal microbiome and suggested microbiome as important functional traits among fish populations.