Bacterial chemotaxis is a colonization factor for the ulcer-causing pathogen Helicobacter pylori. H. pylori contains genes encoding the chemotaxis signalling proteins CheW, CheA and CheY; CheW couples chemoreceptors to the CheA kinase and is essential for chemotaxis. While characterizing a cheW mutant, we isolated a spontaneous, chemotactic variant (Che+). We determined that this phenotype was caused by a genetic change unlinked to the original cheW mutation. To locate the underlying Che+ mutation, we compared total protein profiles of the non-chemotactic mutant (cheW) with those from the cheW Che+ variant by two-dimensional differential in-gel electrophoresis. One protein was found only in the cheW Che+ variant. This protein was identified by MS/MS as HP0170, a hypothetical protein with no known function. DNA sequencing verified that hp0170 was mutated in the cheW Che+ suppressor, and deletion of this open reading frame in the cheW background nearly recapitulated the Che+ suppressor phenotype. Using hidden Markov models, we found that HP0170 is a remote homologue of E. coli CheZ. CheZ interacts with phosphorylated CheY and stimulates its autodephosphorylation. CheZ was not predicted to be present in η-proteobacteria. We found that chemotaxis in the cheW Che+ suppressor depended on both cheY and cheA. We hypothesize that a small amount of phosphorylated CheY is generated via CheA in the cheW mutant, and this amount is sufficient to affect flagellar rotation when HP0170 is removed. Our results suggest that HP0170 is a remote homologue of CheZ, and that CheZ homologues are found in a broader range of bacteria than previously supposed.