The arrival order of species can strongly influence the early assembly of ecological communities. Such events, known as priority effects, are documented in various ecological settings, but remain understudied within the context of the gut microbiome. Given the fundamental link between the gut microbiome and host health, exploring the potential role of priority effects in shaping the assembly and development of microbial communities within the gut becomes imperative. Using the freshwater planktonic crustacean Daphnia magna as a model system, we manipulated the immigration order of three bacterial strain pairs in two germ-free genotypes and quantified gut microbiome composition and host fitness at two time points, namely day 8 and day 12. Priority effects were observed; however, their presence, amplitude, and direction (suppressive or facilitative) were found to be contingent on the identity of bacterial strain and host genotype. These findings were accompanied by notable differences in Daphnia life history traits across inoculation order treatments, shedding light on the tangible consequences of priority effects triggered by the sequence of bacterial strain arrival in the gut environment, for host fitness. Our results thus highlight the complex nature of priority effects in gut community assembly, their strain/genotype specificity, and their potential impact on the host.