P-, E- and L-selectin constitute a family of cell adhesion receptors that mediate the initial tethering and rolling of leukocytes on inflamed endothelium as a prelude to their firm attachment and extravasation into tissues. The selectins bind weakly to sialyl Lewisx (SLe(X))-like glycans, but with high-affinity to specific glycoprotein counterreceptors, including PSGL-1. Here, we report crystal structures of human P- and E-selectin constructs containing the lectin and EGF (LE) domains co-complexed with SLe(X). We also present the crystal structure of P-selectin LE co-complexed with the N-terminal domain of human PSGL-1 modified by both tyrosine sulfation and SLe(X). These structures reveal differences in how E- and P-selectin bind SLe(X) and the molecular basis of the high-affinity interaction between P-selectin and PSGL-1.