We have shown that CD8+ CTLs are the key mediators of accelerated rejection, and that CD8+ T cells represent the prime targets of CD154 blockade in sensitized mouse recipients of cardiac allografts. However, the current protocols require CD154 blockade at the time of sensitization, whereas delayed treatment fails to affect graft rejection in sensitized recipients. To elucidate the mechanisms of costimulation blockade-resistant rejection and to improve the efficacy of CD154-targeted therapy, we found that alloreactive CD8+ T cells were activated despite the CD154 blockade in sensitized hosts. Comparative CD8 T cell activation study in naive vs primed hosts has shown that although both naive and primed/memory CD8+ T cells relied on the CD28 costimulation for their activation, only naive, not primed/memory, CD8+ T cells depend on CD154 signaling to differentiate into CTL effector cells. Adjunctive therapy was designed accordingly to deplete primed/memory CD8+ T cells before the CD154 blockade. Indeed, unlike anti-CD154 monotherapy, transient depletion of CD8+ T cells around the time of cardiac engraftment significantly improved the efficacy of delayed CD154 blockade in sensitized hosts. Hence, this report provides evidence for 1) differential requirement of CD154 costimulation signals for naive vs primed/memory CD8+ T cells, and 2) successful treatment of clinically relevant sensitized recipients to achieve stable long term graft acceptance.