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 Lewis^X (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.