P-selectin glycoprotein ligand-1 (PSGL-1) mediates rolling of leukocytes on P-selectin under flow. The glycoproteins that enable leukocyte tethering to or rolling on E-selectin are not known. We used gene targeting to prepare PSGL-1-deficient (PSGL-1-/-) mice, which were healthy but had moderately elevated total blood leukocytes. Fluid-phase E-selectin bound to approximately 70% fewer sites on PSGL-1-/- than PSGL-1+/+ neutrophils. Compared with PSGL-1+/+ leukocytes, significantly fewer PSGL-1-/- leukocytes rolled on E-selectin in vitro, because their initial tethering to E-selectin was impaired. The residual cells that tethered rolled with the same shear resistance and velocities as PSGL-1+/+ leukocytes. Compared with PSGL-1+/+ mice, significantly fewer PSGL-1-/- leukocytes rolled on E-selectin in TNF-alpha-treated venules of cremaster muscle in which P-selectin function was blocked by an mAb. The residual PSGL-1-/- leukocytes that tethered rolled with slow velocities equivalent to those of PSGL-1+/+ leukocytes. These results reveal a novel function for PSGL-1 in tethering leukocytes to E-selectin under flow.