Earlier studies have suggested that CheZ, the phosphatase of the signaling protein CheY in bacterial chemotaxis, may be in an oligomeric state both when bound to phosphorylated CheY (CheY similar to P) (Blat, Y., and Eisenbach, M. (1994) Biochemistry 33, 902-906) or free (Stock, A., and Stock, J. B. (1987) J. Bacteriol. 169, 3301-3311). The purpose of the current study was to determine the oligomeric state of free CheZ and to investigate whether it changes upon binding to CheY similar to P. By using either one of two different sets of cross-linking agents, free CheZ was found to be a dimer. The formation of the dimer was specific, as it was prevented by SDS which does not interfere with cross-linking mediated by random collisions. The dimeric form of CheZ was confirmed by sedimentation analysis, a cross-linking-free technique. In the presence of CheY similar to P (but not in the presence of non-phosphorylated CheY), a high molecular size crosslinked complex (90-200 kDa) was formed, in which the CheZ:CheY ratio was 2:1. The size of the oligomeric complex was estimated by fluorescence depolarization to be 4-5-fold larger than the dimer, suggesting that its size is in the order of 200 kDa. These results indicate that CheZ oligomerizes upon interaction with CheY similar to P3. This phosphorylation-dependent oligomerization may be a mechanism for regulating CheZ activity.