Animals and their associated microbiota share long evolutionary histories. However, it is not always clear how host genotype and microbiota interact to affect phenotype. We applied a hologenomic approach to explore how host-microbiota interactions shape lifetime growth and parasite infection in farmed Atlantic salmon (Salmo salar). Multi-omics data sets were generated from the guts of 460 salmon, 82% of which were naturally infected with an intestinal cestode. A single Mycoplasma bacterial strain, MAG01, dominated the gut metagenome of large, non-parasitized fish, consistent with previous studies showing high levels of Mycoplasma in the gut microbiota of healthy salmon. While small and/or parasitized salmon also had high abundance of MAG01, we observed increased alpha diversity in these individuals, driven by increased frequency of low-abundance Vibrionaceae and other Mycoplasma species that carried known virulence genes. Colonization by one of these cestode-associated Mycoplasma strains was associated with host individual genomic variation in long non-coding RNAs. Integrating the multi-omic data sets revealed coordinated changes in the salmon gut mRNA transcriptome and metabolome that correlated with shifts in the microbiota of smaller, parasitized fish. Our results suggest that the gut microbiota of small and/or parasitized fish is in a state of dysbiosis that partly depends on the host genotype, highlighting the value of using a hologenomic approach to incorporate the microbiota into the study of host-parasite dynamics.IMPORTANCEStudying host-microbiota interactions through the perspective of the hologenome is gaining interest across all life sciences. Intestinal parasite infections are a huge burden on human and animal health; however, there are few studies investigating the role of the hologenome during parasite infections. We address this gap in the largest multi-omics fish microbiota study to date using natural cestode infection of farmed Atlantic salmon. We find a clear association between cestode infection, salmon lifetime growth, and perturbation of the salmon gut microbiota. Furthermore, we provide the first evidence that the genetic background of the host may partly determine how the gut microbiota changes during parasite-associated dysbiosis. Our study therefore highlights the value of a hologenomic approach for gaining a more in-depth understanding of parasitism.