Evolutionary relationships among species are often assumed to be fundamentally unambiguous, where genes within a genome are thought to evolve in concert and phylogenetic incongruence between individual orthologs is attributed to idiosyncrasies in their evolution. We have identified substantial incongruence between the phylogenies of orthologous genes in Escherichia, Salmonella, and Citrobacter, or E. coli, E. fergusonii, and E. albertii. The source of incongruence was inferred to be recombination, because individual genes support conflicting topology more robustly than expected from stochastic sequence homoplasies. Clustering of phylogenetically informative sites on the genome indicated that the regions of recombination extended over several kilobases. Analysis of phylogenetically distant taxa resulted in consensus among individual gene phylogenies, suggesting that recombination is not ongoing; instead, conflicting relationships among genes in descendent taxa reflect recombination among their ancestors. Incongruence could have resulted from random assortment of ancestral polymorphisms if species were instantly created from the division of a recombining population. However, the estimated branch lengths in alternative phylogenies would require ancestral populations with far more diversity than is found in extant populations. Rather, these and previous data collectively suggest that genome-wide recombination rates decreased gradually, with variation in rate among loci, leading to pluralistic relationships among their descendent taxa.