Allogeneic blood or BM transplantation (BMT) is the most commonly applied form of adoptive cellular therapy for cancer. In this context, the ability of donor T cells to respond to recipient antigens is coopted to generate graft-versus-tumor (GVT) responses. The major reason for treatment failure is tumor recurrence, which is linked to the eventual loss of functional, host-specific CTLs. In this study, we have explored the role of recipient antigen expression by nonhematopoietic cells in the failure to sustain effective CTL immunity. Using clinically relevant models, we found that nonhematopoietic antigen severely disrupts the formation of donor CD8+ T cell memory at 2 distinct levels that operate in the early and late phases of the response. First, initial and direct encounters between donor CD8+ T cells and nonhematopoietic cells blocked the programming of memory precursors essential for establishing recall immunity. Second, surviving CD8+ T cells became functionally exhausted with heightened expression of the coinhibitory receptor programmed death-1 (PD-1). These 2 factors acted together to induce even more profound failure in long-term immunosurveillance. Crucially, the functions of exhausted CD8+ T cells could be partially restored by late in vivo blockade of the interaction between PD-1 and its ligand, PD-L1, without induction of graft-versus-host disease, suggestive of a potential clinical strategy to prevent or treat relapse following allogeneic BMT.