Transplant tolerance, defined as indefinite allograft survival without immunosuppression, has been regularly achieved in laboratory mice but not in nonhuman primates or humans. In contrast to laboratory mice, primates regularly have high frequencies of alloreactive memory T cells (TMEMs) before transplantation. These TMEMs are poorly sensitive to conventional immunosuppression and costimulation blockade, and the presence of donor-reactive TMEMs in primates may account for their resistance to transplant tolerance protocols that have proven consistently effective in mice. We measured the frequencies of anti-donor TMEMs before and after transplantation in a series of rejecting and tolerant monkeys that underwent nonmyeloablative conditioning, short-term immunosuppression, and combined allogeneic kidney/cell transplantation. Transplants were acutely rejected in all the monkeys with high numbers of donor-specific TMEMs before transplantation. In contrast, long-term survival was observed in the recipients harboring lower frequencies of anti-donor TMEMs before transplantation. Similar amounts of TMEM homeostatic expansion were recorded in all transplanted monkeys upon hematopoietic reconstitution; however, only the tolerant monkeys had no expansion or activation of donor-reactive TMEMs after transplantation. These results indicate that the presence of high frequencies of host donor-reactive TMEMs before transplantation impairs tolerance induction to kidney allografts in this nonhuman primate model. Indeed, recipients harboring a low anamnestic reactivity to their donor before transplantation were successfully rendered tolerant via infusion of donor cells and short-term immunosuppression. This suggests that selection of allogeneic donors with low memory responses in recipients may be essential to successful transplant tolerance induction in patients.