Fecal microbiota transplantation is a highly effective intervention for patients suffering from recurrent Clostridium difficile, a common hospital-acquired infection. Fecal microbiota transplantation’s success as a therapy for C. difficile has inspired interest in performing clinical trials that experiment with fecal microbiota transplantation as a therapy for other conditions like inflammatory bowel disease, obesity, diabetes, and Parkinson’s disease. Results from clinical trials that use fecal microbiota transplantation to treat inflammatory bowel disease suggest that, for at least one condition beyond C. difficile, most fecal microbiota transplantation donors produce stool that is not efficacious. The optimal strategies for identifying and using efficacious donors have not been investigated. We therefore examined the optimal Bayesian response-adaptive strategy for allocating patients to donors and formulated a computationally tractable myopic heuristic. This heuristic computes the probability that a donor is efficacious by updating prior expectations about the efficacy of fecal microbiota transplantation, the placebo rate, and the fraction of donors that produce efficacious stool. In simulations designed to mimic a recent fecal microbiota transplantation clinical trial, for which traditional power calculations predict ∼100% statistical power, we found that accounting for differences in donor stool efficacy reduced the predicted statistical power to ∼9%. For these simulations, using the heuristic Bayesian allocation strategy more than quadrupled the statistical power to ∼39%. We use the results of similar simulations to make recommendations about the number of patients, the number of donors, and the choice of clinical endpoint that clinical trials should use to optimize their ability to detect if fecal microbiota transplantation is effective for treating a condition.