Many strategies have been proposed to induce tolerance to transplanted tissue in rodents; however, few if any have shown equal efficacy when tested in nonhuman primate transplant models. We hypothesized that a critical distinction between specific pathogen-free mice and nonhuman primates or human patients is their acquired immune history. Here, we show that a heterologous immune response--specifically, virally induced alloreactive memory--is a potent barrier to tolerance induction. A critical threshold of memory T cells is needed to promote rejection, and CD8(+) "central" memory T cells are primarily responsible. Finally, treatment with deoxyspergualin, an inhibitor of NF-kappa B translocation, together with costimulation blockade, synergistically impairs memory T cell activation and promotes antigen-specific tolerance of memory. These data offer a potential explanation for the difficulty encountered when inducing tolerance in nonhuman primates and human patients and provide insight into the signaling pathways essential for memory T cell activation and function.