Fundamental restoration ecology and community ecology theories can help us better understand the underlying mechanisms of fecal microbiota transplantation (FMT) and to better design future microbial therapeutics for recurrent Clostridioides difficile infections (rCDI) and other dysbiosis-related conditions. In this study, stool samples were collected from donors and rCDI patients one week prior to FMT (pre-FMT), as well as from patients one week following FMT (post-FMT). Using metagenomic sequencing and machine learning, our results suggested that FMT outcome is not only dependent on the ecological structure of the recipients, but also the interactions between the donor and recipient microbiomes at the taxonomical and functional levels. We observed that the presence of specific bacteria in donors (Clostridioides spp., Desulfovibrio spp., Odoribacter spp. and Oscillibacter spp.) and the absence of fungi (Yarrowia spp.) and bacteria (Wigglesworthia spp.) in recipients prior to FMT could predict FMT success. Our results also suggested a series of interlocked mechanisms for FMT success, including the repair of the disturbed gut ecosystem by transient colonization of nexus species followed by secondary succession of bile acid metabolizers, sporulators, and short chain fatty acid producers.