CD28 costimulatory blockade induces tolerance in most murine transplant models but fails to do so in stringent transplant models, such as skin transplantation. The precise immunological mechanisms of CD28-independent rejection remain to be fully defined. Using two novel mouse strains in which both CD28 and either CD4 or CD8 are knocked out (CD4(-/-)CD28(-/-) or CD8(-/-)CD28(-/-) mice), we examined mechanisms of CD28-independent CD4(+) or CD8(+) T-cell-mediated allograft rejection. CD4(-/-)CD28(-/-) and CD8(-/-)CD28(-/) deficient mice rejected fully allogeneic skin allografts at a tempo comparable with that in wild-type mice. Rejection proceeded despite significant reduction in alloreactive T-cell clone sizes suggesting the presence of a subset of T cells harnessing alternate CD28-independent costimulatory pathways. Blockade of CD40-CD154 and CD134-CD134L, but not ICOS-B7h pathways in combination significantly prolonged allograft survival in CD8(-/-)CD28(-/-) recipients and to a lesser extent in CD4(-/-)CD28(-/-) recipients. Prolongation in allograft survival was associated with reduced effector-memory T-cell generation, decreased allospecific Th1 cytokine generation and diminished alloreactive T-cell proliferation in vivo. In aggregate, the data identify these two pathways as critical mediators of CD28-independent rejection by CD4(+) and to a lesser extent CD8(+) T cells, and provide novel mechanistic insights into functions of novel T-cell co-stimulatory pathways in vivo.