The selective pressure by infectious agents is a major driving force in the evolution of humans and other mammals. Members of the carcinoembryonic antigen-related cell adhesion molecule (CEACAM) family serve as receptors for bacterial pathogens of the genera Haemophilus, Helicobacter, Neisseria, and Moraxella, which engage CEACAMs via distinct surface adhesins. While microbial attachment to epithelial CEACAMs facilitates host colonization, recognition by CEACAM3, a phagocytic receptor expressed by granulocytes, eliminates CEACAM-binding bacteria. Sequence analysis of primate CEACAM3 orthologs reveals that this innate immune receptor is one of the most rapidly evolving human proteins. In particular, the pathogen-binding extracellular domain of CEACAM3 shows a high degree of non-synonymous versus synonymous nucleotide exchanges, indicating an exceptionally strong positive selection. Using CEACAM3 domains derived from different primates, we find that the amino acid alterations found in CEACAM3 translate into characteristic binding patterns for bacterial adhesins. One such amino acid residue is F62 in human and chimp CEACAM3, which is not present in other primates and which is critical for binding the OMP P1 adhesin of Haemophilus aegyptius. Incorporation of the F62-containing motif into gorilla CEACAM3 results in a gain-of-function phenotype with regard to phagocytosis of H. aegyptius. Moreover, CEACAM3 polymorphisms found in human subpopulations widen the spectrum of recognized bacterial adhesins, suggesting an ongoing multivariate selection acting on this innate immune receptor. The species-specific detection of diverse bacterial adhesins helps to explain the exceptionally fast evolution of CEACAM3 within the primate lineage and provides an example of Red Queen dynamics in the human genome.