Distinct populations of effector memory T cells use different homing receptors to traffic to the skin and gut. Whether tissue-selective T cells are needed for early rejection of a neoplasm growing in these tissues remains an open question. We chose to study an allogeneic tumor model because growth of such a fully mismatched tumor would signify a profound immune deficit. We implanted allogeneic tumor cells in the skin or gut of mice deficient in either α(1,3) fucosyltransferases IV and VII, enzymes critical for generating E-selectin ligands on skin-homing T cells, or β7 integrin, a component of the α4β7 integrin ligand for the mucosal adressin MAdCAM. During the first 9 days after tumor implantation, FucTVII-/- mice showed a profoundly impaired capacity to reject tumors growing in the skin, but readily rejected tumors implanted in the gut. Rejection of tumors in the skin was even more impaired in mice deficient in both FucTIV and FucTVII. This impairment was corrected by infusion of T cells from normal mice. By contrast, β7 integrin-/- mice showed profoundly impaired rejection of tumors in the gut, but no defect in the skin tumor rejection. These differences were unrelated to antigen recognition or effector function of T cells, since all strains of mice were capable of generating tumor-specific CTLs in vitro against the tumor cell line used in vivo. These results demonstrate that T-cell homing defects in vivo impair immune surveillance of peripheral epithelial tissues in a specific and selective fashion.