Fecal microbiota transplantation (FMT) from healthy donor to patient is a treatment for microbiome-associated diseases. Although the success of FMT requires donor bacteria to engraft in the patient's gut, the forces governing engraftment in humans are unknown. Here we use an ongoing clinical experiment, the treatment of recurrent Clostridium difficile infection, to uncover the rules of engraftment in humans. We built a statistical model that predicts which bacterial species will engraft in a given host, and developed Strain Finder, a method to infer strain genotypes and track them over time. We find that engraftment can be predicted largely from the abundance and phylogeny of bacteria in the donor and the pre-FMT patient. Furthermore, donor strains within a species engraft in an all-or-nothing manner and previously undetected strains frequently colonize patients receiving FMT. We validated these findings for metabolic syndrome, suggesting that the same principles of engraftment extend to other indications.