Background: Animal protein production is increasingly looking towards microbiome-associated services such as the design of new and better probiotic solutions to further improve gut health and production sustainability. Here, we investigate the functional effects of bacteria-based pro- and synbiotic feed additives on microbiome-associated functions in relation to growth performance in the commercially important rainbow trout (Oncorhynchus mykiss). We combine complementary insights from multiple omics datasets from gut content samples, including 16S bacterial profiling, whole metagenomes, and untargeted metabolomics, to investigate bacterial metagenome-assembled genomes (MAGs) and their molecular interactions with host metabolism. Results: Our findings reveal that (I) feed additives changed the microbiome and that rainbow trout reared with feed additives had a significantly reduced relative abundance of the salmonid related Candidatus Mycoplasma salmoninae in both the mid and distal gut content, (II) genome resolved metagenomics revealed that alterations of microbial arginine biosynthesis and terpenoid backbone synthesis pathways were directly associated with the presence of Candidatus Mycoplasma salmoninae, and (III) differences in the composition of intestinal microbiota among feed types were directly associated with significant changes of the metabolomic landscape, including lipids and lipid-like metabolites, amino acids, bile acids, and steroid-related metabolites. Conclusion: Our results demonstrate how the use of multi-omics to investigate complex host-microbiome interactions enable us to better evaluate the functional potential of probiotics compared to studies that only measure overall growth performance or that only characterise the microbial composition in intestinal environments. [MediaObject not available: see fulltext.]