Aspartyl-phosphate phosphatases underlie the rapid responses of bacterial chemotaxis. One such phosphatase, CheZ, was originally proposed to be restricted to beta and gamma proteobacter, suggesting only a small subset of microbes relied on this protein. A putative CheZ phosphatase was identified genetically in the epsilon proteobacter Helicobacter pylori (Mol Micro 61:187). H. pylori utilizes a chemotaxis system consisting of CheAY, three CheVs, CheW, CheY(HP) and the putative CheZ to colonize the host stomach. Here we investigate whether this CheZ has phosphatase activity. We phosphorylated potential targets in vitro using either a phosphodonor or the CheAY kinase and [gamma-(32)P]-ATP, and found that H. pylori CheZ (CheZ(HP)) efficiently dephosphorylates CheY(HP) and CheAY and has additional weak activity on CheV2. We detected no phosphatase activity towards CheV1 or CheV3. Mutations corresponding to Escherichia coli CheZ active site residues or deletion of the C-terminal region inactivate CheZ(HP) phosphatase activity, suggesting the two CheZs function similarly. Bioinformatics analysis suggests that CheZ phosphatases are found in all proteobacteria classes, as well as classes Aquificae, Deferribacteres, Nitrospira and Sphingobacteria, demonstrating that CheZ phosphatases are broadly distributed within Gram-negative bacteria.