Chemoreceptor-based signaling pathways are among the major modes of bacterial signal transduction, and Pseudomonas aeruginosa PAO1 is an important model to study their function. Of the 26 chemoreceptors of this strain, PctA has a broad ligand range and responds to most of the proteinogenic amino acids, whereas PctB and PctC have a much narrower range and show strong ligand preference for l-glutamine and γ-aminobutyrate, respectively. Using several comparative genomics approaches, we show that these receptors are paralogs: pctA gene duplication in the common ancestor of the genus Pseudomonas led to pctC, whereas pctB originated through another, independent pctA duplication in the common ancestor of P. aeruginosa. Thus, the broad-range amino acid chemoreceptor was evolutionarily older, and chemoreceptors that complemented “missing” amino acid sensing abilities arose later in specific Pseudomonas lineages. Using comparative sequence analysis, newly solved crystal structures of PctA, PctB, and PctC ligand-binding domains, and their molecular dynamics simulations, we identified a conserved amino acid recognition motif and changes in the ligand-binding pocket that led to novel ligand specificities. In addition, we determined major forces driving the evolution of this group of chemoreceptors.