Adaptation to persisting stimulation is required for highly sensitive detection of temporal changes of stimuli, and often involves covalent modification of receptors. Therefore, it is of vital importance to understand how a receptor and its cognate modifying enzyme(s) modulate each other through specific protein-protein interactions. In the chemotaxis of Escherichia coli, adaptation requires methylation of chemoreceptors (e.g. Tar) catalyzed by the CheR methyltransferase. CheR binds to the C-terminal NWETF sequence of a chemoreceptor that is distinct from the methylation sites. However, little is known about how CheR recognizes its methylation sites or how it is distributed in a cell. In this study, we used comparative genomics to demonstrate that the CheR chemotaxis methyltransferase contains three structurally and functionally distinct modules: (i) the catalytic domain common to a methyltransferase superfamily; (ii) the N-terminal domain; and (iii) the beta-subdomain of the catalytic domain, both of which are found exclusively in chemotaxis methyltransferases. The only evolutionary conserved motif specific to CheR is the positively charged face of helix alpha2 in the N-terminal domain. The disulfide cross-linking analysis suggested that this face interacts with the methylation helix of Tar. We also demonstrated that CheR localizes to receptor clusters at cell poles via interaction of the beta-subdomain with the NWETF sequence. Thus, the two chemotaxis-specific modules of CheR interact with distinct regions of the chemoreceptor for targeting to the receptor cluster and for recognition of the substrate sites, respectively.