P-selectin binding to neutrophils requires a specific protein, P-selectin glycoprotein ligand 1 (PSGL-1), as well as sialyl-Lewis X (sLex) glycan determinants. We have found that a short segment near the amino terminus of PSGL-1 that contains a tyrosine sulfation consensus is essential for P-selectin adhesion and that addition of the amino-terminal segment to some but not all mucin-like molecules confers on those molecules the ability to bind P-selectin. PSGL-1 synthesized in the presence of sulfation inhibitors binds P-selectin weakly, and within the amino-terminal 20 residues, mutation of the tyrosines to phenylalanine abolishes binding. Rolling of HL-60 cells on P-selectin-coated coverslips is strongly attenuated by treatment of cells with an inhibitor of sulfation.