Leukocyte trafficking at the endothelium requires both cellular adhesion molecules and chemotactic factors. Fractalkine, a novel transmembrane molecule with a CX₃C-motif chemokine domain atop a mucin stalk, induces both adhesion and migration of leukocytes. Here we identify a seven-transmembrane high-affinity receptor for fractalkine and show that it mediates both the adhesive and migratory functions of fractalkine. The receptor, now termed CX₃CR1, requires pertussis toxin–sensitive G protein signaling to induce migration but not to support adhesion, which also occurs without other adhesion molecules but requires the architecture of a chemokine domain atop the mucin stalk. Natural killer cells predominantly express CX₃CR1 and respond to fractalkine in both migration and adhesion. Thus, fractalkine and CX₃CR1 represent new types of leukocyte trafficking regulators, performing both adhesive and chemotactic functions.