In bacterial chemotaxis, phosphorylated CheY levels control the sense of flagella rotation and thereby determine swimming behavior. In E. coli, CheY dephosphorylation by CheZ extinguishes the switching signal. But, instead of CheZ, many chemotactic bacteria contain CheC, CheD, and/or CheX. The crystal structures of T. maritima CheC and CheX reveal a common fold unlike that of any other known protein. Unlike CheC, CheX dimerizes via a continuous beta sheet between subunits. T. maritima CheC, as well as CheX, dephosphorylate CheY, although CheC requires binding of CheD to achieve the activity of CheX. Structural analyses identified one conserved active site in CheX and two in CheC; mutations therein reduce CheY-phosphatase activity, but only mutants of two invariant asparagine residues are completely inactive even in the presence of CheD. Our structures indicate that the flagellar switch components FliY and FliM resemble CheC more closely than CheX, but attribute phosphatase activity only to FliY.