ABSTRACT Chemotaxis allows bacteria to more efficiently colonize optimal microhabitats within their larger environment. Chemotaxis in Escherichia coli is the best-studied model system, and a large number of E. coli strains have been sequenced. The Escherichia/Shigella genus encompasses a great variety of commensal and pathogenic strains, but the role of chemotaxis in their association with the host remains poorly understood. Here we show that the core chemotaxis genes are lost in many, but not all, nonmotile strains but are well preserved in all motile strains. The genes encoding the Tar, Tsr, and Aer chemoreceptors, which mediate chemotaxis to a broad spectrum of chemical and physical cues, are also nearly uniformly conserved in motile strains. In contrast, the clade of extraintestinal pathogenic E. coli strains apparently underwent an ancestral loss of Trg and Tap chemoreceptors, which sense sugars, dipeptides, and pyrimidines. The broad range of time estimated for the loss of these genes (1 to 3 million years ago) corresponds to the appearance of the genus Homo .