Fecal microbiota transplantation (FMT) is a therapeutic intervention for inflammatory diseases of the gastrointestinal tract, but its clinical mode of action and subsequent microbiome dynamics remain poorly understood. Here we analyzed metagenomes from 316 FMTs, sampled pre and post intervention, for the treatment of ten different disease indications. We quantified strain-level dynamics of 1,089 microbial species, complemented by 47,548 newly constructed metagenome-assembled genomes. Donor strain colonization and recipient strain resilience were mostly independent of clinical outcomes, but accurately predictable using LASSO-regularized regression models that accounted for host, microbiome and procedural variables. Recipient factors and donor-recipient complementarity, encompassing entire microbial communities to individual strains, were the main determinants of strain population dynamics, providing insights into the underlying processes that shape the post-FMT gut microbiome. Applying an ecology-based framework to our findings indicated parameters that may inform the development of more effective, targeted microbiome therapies in the future, and suggested how patient stratification can be used to enhance donor microbiota colonization or the displacement of recipient microbes in clinical practice.