Toll-like receptor 5 (TLR5) recognizes an evolutionarily conserved site on bacterial flagellin that is required for flagellar filament assembly and motility. The α and ε Proteobacteria, including the important human pathogens Campylobacter jejuni, Helicobacter pylori, and Bartonella bacilliformis, require flagellar motility to efficiently infect mammalian hosts. In this study, we demonstrate that these bacteria make flagellin molecules that are not recognized by TLR5. We map the site responsible for TLR5 evasion to amino acids 89-96 of the N-terminal D1 domain, which is centrally positioned within the previously defined TLR5 recognition site. Salmonella flagellin is strongly recognized by TLR5, but mutating residues 89-96 to the corresponding H. pylori flaA sequence abolishes TLR5 recognition and also destroys bacterial motility. To preserve bacterial motility, α and ε Proteobacteria possess compensatory amino acid changes in other regions of the flagellin molecule, and we engineer a mutant form of Salmonella flagellin that evades TLR5 but retains motility. These results suggest that TLR5 evasion is critical for the survival of this subset of bacteria at mucosal sites in animals and raise the intriguing possibility that flagellin receptors provided the selective force to drive the evolution of these unique subclasses of bacterial flagellins.