Communication among bacterial cells through quorum-sensing (QS) systems is used to regulate ecologically and medically important traits, including virulence to hosts. QS is widespread in bacteria; it has been demonstrated experimentally in diverse phylogenetic groups, and homologs to the implicated genes have been discovered in a large proportion of sequenced bacterial genomes. The widespread distribution of the underlying gene families (LuxI/R and LuxS) raises the questions of how often QS genes have been transferred among bacterial lineages and the extent to which genes in the same QS system exchange partners or coevolve. Phylogenetic analyses of the relevant gene families show that the genes annotated as LuxI/R inducer and receptor elements comprise two families with virtually no homology between them and with one family restricted to the gamma-Proteobacteria and the other more widely distributed. Within bacterial phyla, trees for the LuxS and the two LuxI/R families show broad agreement with the ribosomal RNA tree, suggesting that these systems have been continually present during the evolution of groups such as the Proteobacteria and the Firmicutes. However, lateral transfer can be inferred for some genes (e.g., from Firmicutes to some distantly related lineages for LuxS). In general, the inducer/receptor elements in the LuxI/R systems have evolved together with little exchange of partners, although loss or replacement of partners has occurred in several lineages of gamma-Proteobacteria, the group for which sampling is most intensive in current databases. For instance, in Pseudomonas aeruginosa, a transferred QS system has been incorporated into the pathway of a native one. Gene phylogenies for the main LuxI/R family in Pseudomonas species imply a complex history of lateral transfer, ancestral duplication, and gene loss within the genus.