Probiotics are intended to improve gastrointestinal health when consumed. However, the probiotics marketed today only colonize the densely populated gut to a limited extent. Bacteriophages comprise the majority of viruses in the human gut virome and there are strong indications that they play important roles in shaping the gut microbiome. Here, we investigate the use of fecal virome transplantation (FVT, sterile filtrated feces) as a mean to alter the gut microbiome composition to lead the way for persistent colonization of two types of probiotics: Lacticaseibacillus rhamnosus GG (LGG) representing a well-established probiotic and Akkermansia muciniphila (AKM) representing a putative next-generation probiotic. Male and female C57BL/6NTac mice were cohoused in pairs from 4 weeks of age and received the following treatment by oral gavage at week 5 and 6: AKM+FVT, LGG+FVT, probiotic sham (Pro-sham)+FVT, LGG+Saline, AKM+Saline, and control (Pro-sham+Saline). The FVT donor material originated from mice with high relative abundance of A. muciniphila. All animals were terminated at age 9 weeks. The FVT treatment did not increase the relative abundance of the administered LGG or AKM in the recipient mice. Instead FVT significantly (p < 0.05) increased the abundance of naturally occurring A.muciniphila compared to the control. This highlights the potential of propagating the existing commensal “probiotics” that have already permanently colonized the gut. Being co-housed male and female, a fraction of the female mice became pregnant. Unexpectedly, the FVT treated mice were found to have a significantly (p < 0.05) higher fertility rate independent of probiotic administration. These preliminary observations urge for follow-up studies investigating interactions between the gut microbiome and fertility.