Fecal microbiota transplantation (FMT) has been successfully applied to treat recurrent Clostridium difficile infection in humans, but a precise method to measure which bacterial strains stably engraft in recipients and evaluate their association with clinical outcomes is lacking. We assembled a collection of >1,000 different bacterial strains that were cultured from the fecal samples of 22 FMT donors and recipients. Using our strain collection combined with metagenomic sequencing data from the same samples, we developed a statistical approach named Strainer for the detection and tracking of bacterial strains from metagenomic sequencing data. We applied Strainer to evaluate a cohort of 13 FMT longitudinal clinical interventions and detected stable engraftment of 71% of donor microbiota strains in recipients up to 5 years post-FMT. We found that 80% of recipient gut bacterial strains pre-FMT were eliminated by FMT and that post-FMT the strains present persisted up to 5 years later, together with environmentally acquired strains. Quantification of donor bacterial strain engraftment in recipients independently explained (precision 100%, recall 95%) the clinical outcomes (relapse or success) after initial and repeat FMT. We report a compendium of bacterial species and strains that consistently engraft in recipients over time that could be used in defined live biotherapeutic products as an alternative to FMT. Our analytical framework and Strainer can be applied to systematically evaluate either FMT or defined live bacterial therapeutic studies by quantification of strain engraftment in recipients.