Chemokine CXCL16 and its receptor CXCR6 are associated with a series of physiological and pathological processes in cooperative and stand-alone fashions. To shed insight into their versatile nature, we studied genetic variations of CXCL16 and CXCR6 in primates. Evolutionary analyses revealed that these genes underwent a similar evolutionary fate. Both genes experienced adaptive diversification with the phylogenetic division of cercopithecoids (Old World monkeys) and hominoids (humans, great apes, and gibbons) from their common ancestor. In contrast, they were conserved in the periods preceding and following the dividing process. In terms of the adaptive diversification between cercopithecoids and hominoids, the adaptive genetic changes have occurred in the mucin-like and chemokine domains of CXCL16 and the N-terminus and transmembrane helixes of CXCR6. In combination with currently available structural and functional information for CXCL16 and CXCR6, the parallels between the evolutionary footprints and the co-occurrence of adaptive diversification at some evolutionary stage suggest that interplay could exist between the diversification-related amino acid sites, or between the domains on which the identified sites are located, in physiological processes such as chemotaxis and/or cell adhesion.