Blockade of T-cell costimulatory pathways represents a potent and specific method of preventing naïve antidonor T-cell responses after transplantation in mouse, monkey, and man. However, numerous studies have shown that the presence of donor-reactive memory T cells in the recipient poses a sometimes insurmountable barrier to long-term graft survival and tolerance induction. Here, we discuss the ways in which donor-reactive memory T cells may arise from environmental exposure to pathogens. Pathogen-specific memory T cells, by virtue of the inherent degeneracy of T-cell receptor recognition of peptide:major histocompatibility complex ligands, may exhibit cross reactivity with allogeneic peptide:major histocompatibility complexes and thereby mediate graft rejection. From the recent explosion in knowledge of the heterogeneity of memory T-cell resulting from variations in frequency and duration of antigen exposure, cytokine milieu, site of priming, and a host of other factors, it is becoming increasingly well appreciated that different memory T-cell populations may exhibit differential susceptibilities to tolerance induction. Thus, the immune history of a transplant recipient and frequencies of donor-cross-reactive memory T cells within the various compartments may dictate the likelihood of success or failure of tolerance induction.