Some arsenite [As(III)]-oxidizing bacteria exhibit positive chemotaxis towards As(III), however, the related As(III) chemoreceptor and regulatory mechanism remain unknown. The As(III)-oxidizing bacterium Agrobacterium tumefaciens GW4 displays positive chemotaxis towards 0.5-2 mM As(III). Genomic analyses revealed a putative chemoreceptor-encoding gene, mcp, located in the arsenic gene island and having a predicted promoter binding site for the As(III) oxidation regulator AioR. Expression of mcp and other chemotaxis related genes (cheA, cheY2 and fliG) was inducible by As(III), but not in the aioR mutant. Using capillary assays and intrinsic tryptophan fluorescence spectra analysis, Mcp was confirmed to be responsible for chemotaxis towards As(III) and to bind As(III) (but not As(V) nor phosphate) as part of the sensing mechanism. A bacterial one-hybrid system technique and electrophoretic mobility shift assays showed that AioR interacts with the mcp regulatory region in vivo and in vitro, and the precise AioR binding site was confirmed using DNase I foot-printing. Taken together, these results indicate that this Mcp is responsible for the chemotactic response towards As(III) and is regulated by AioR. Additionally, disrupting the mcp gene affected bacterial As(III) oxidation and growth, inferring that Mcp may exert some sort of functional connection between As(III) oxidation and As(III) chemotaxis.