Selectin-selectin ligand interactions mediate the initial steps in leukocyte migration, an integral part of immune responses. Fucosyltransferase-VII (FucT-VII), encoded by Fut7, is essential for biosynthesis of selectin ligands. In an established model of cardiac allograft vasculopathy and chronic rejection, Fut7(-/-) recipients exhibited long-term graft survival with minimal vasculopathy compared with WT controls. Graft survival was associated with CD4 T-cell exhaustion in the periphery, characterized by impaired effector cytokine production, defective proliferation, increased expression of inhibitory receptors programmed death-1 (PD-1) and T cell Ig- and mucin-domain-containing molecule-3 (Tim-3), low levels of IL-7Rα on CD4 T cells, and reduced migration of polyfunctional CD4 memory T cells to the allograft. Blocking PD-1 triggered rejection only in Fut7(-/-) recipients, whereas depleting regulatory T cells had no effect in either Fut7(-/-) or WT recipients. Adoptive transfer experiments confirmed that this CD4 T cell-exhausted phenotype is seen primarily in Fut7(-/-) CD4 T cells. These data suggest that impaired leukocyte recruitment is a novel mechanism leading to CD4 T-cell exhaustion. Our experimental system serves as an excellent model to study CD4 T-cell exhaustion as a dominant mechanism of transplant tolerance. Further, targeting FucT-VII may serve as a promising strategy to prevent chronic allograft rejection and promote tolerance.