Molecules involved in leukocyte trafficking have a central role in the development of inflammatory and immune responses. We performed F(ST) analysis of the selectin cluster, as well as of SELPLG, ICAM1 and VCAM1. Peaks of significantly high population genetic differentiation were restricted to two regions in SELP and one in SELPLG. Resequencing data indicated that the region covering SELP exons 11-13 displays high nucleotide diversity in Africans and Europeans (CEU), and a high level of within-species diversity compared with inter-specific divergence. Analysis of inferred haplotypes revealed a complex phylogeny with two deeply separated clades that coalesce at ~3.5 million years (MY) plus a minor clade with a TMRCA (time to the most recent common ancestor) of ~2.2 MY. A splicing assay indicated no haplotype-specific effect on SELP exon 14 inclusion. These data are consistent with a model of multiallelic balancing selection; single-nucleotide polymorphism analysis indicated that the Val640Leu variant represents a likely selection target. In populations of Asian ancestry a distinct haplotype, possibly carrying regulatory variants, has been driven to high frequency by positive selection. No deviation from neutrality was observed for the SELPLG region. Resequencing of SELP in chimpanzees revealed a haplotype phylogeny with extremely deep basal branches, suggesting either long-standing balancing selection or ancestral population structure. Thus, SELP has experienced a complex selective history, possibly as a result of local adaptation. Variants in the gene have been associated with autoimmune and cardiovascular diseases. Association studies would benefit from both taking the complex SELP haplotype structure into account and from analysis of possible regulatory variants in the gene.