Natural killer (NK) cells are components of the innate immune system that can recognize and kill virally infected cells, tumor cells, and allogeneic cells without prior sensitization. NK cells also elaborate cytokines (e.g., interferon-gamma and tumor necrosis factor-alpha) and chemokines (e.g., macrophage inflammatory protein-1alpha) that promote the acquisition of antigen-specific immunity. NK cell differentiation is accompanied by the cell surface expression of a mucin-like glycoprotein bearing an NK cell-restricted keratan sulfate-related lactosamine carbohydrate, the PEN5 epitope. Here, we report that PEN5 is a post-translational modification of P-selectin glycoprotein ligand-1 (PSGL-1). The PEN5 epitope creates on PSGL-1 a unique binding site for L-selectin, which is independent of PSGL-1 tyrosine sulfation. On the surface of NK cells, the expression of PEN5 is coordinated with the disappearance of L-selectin and the up-regulation of Killer cell Ig-like Receptors (KIR). These results indicate that NK cell differentiation is accompanied by the acquisition of a unique carbohydrate, PEN5, that can serve as part of a combination code to deliver KIR(+) NK cells to specific tissues.