Chemokine receptors and their counterpart ligands are one of the evolutionary innovations of vertebrates. They play a guiding role in the coordination of cell trafficking in many biological processes. Comparative syntenic and phylogenetic analyses provide insight into the evolution of chemokine receptors and suggest that the repertoire of chemokine receptors varies in each species, regardless of the evolutionary position of the species. Despite the rapid evolution of chemokine receptors, the expression and function of orthologous chemokine receptors in lower and higher vertebrates are very similar. This is also true for the chemokine ligands that have been examined so far, such as CXCL8, CXCL12, and CCL25. As examples, this review will discuss how the evolution of the chemokine receptor CXCR4 is coincident with the emergence of lymphocytes in jawless vertebrates (lamprey); and that, in jawed vertebrates, CXCR4 and CCR9 are involved in thymus colonization. In myeloid cells, the function of CXCR1 in neutrophils and the expression of CXCR3 in macrophages and DCs are evolutionarily conserved between fish and mammals. In this context, medaka and zebrafish are outstanding models for studying the function of chemokines and their receptors.