In Shewanella sp. strain ANA-3, utilization of arsenate as a terminal electron acceptor is conferred by a two-gene operon, arrAB, which lacks a gene encoding a membrane-anchoring subunit for the soluble ArrAB protein complex. Analysis of the genome sequence of Shewanella putrefaciens strain CN-32 showed that it also contained the same arrAB operon with 100% nucleotide identity. Here, we report that CN-32 respires arsenate and that this metabolism is dependent on arrA and an additional gene encoding a membrane-associated tetraheme c-type cytochrome, cymA. Deletion of cymA in ANA-3 also eliminated growth on and reduction of arsenate. The DeltacymA strains of CN-32 and ANA-3 negatively affected the reduction of Fe(III) and Mn(IV) but not growth on nitrate. Unlike the CN-32 DeltacymA strain, growth on fumarate was absent in the DeltacymA strain of ANA-3. Both homologous and heterologous complementation of cymA in trans restored growth on arsenate in DeltacymA strains of both CN-32 and ANA-3. Transcription patterns of cymA showed that it was induced under anaerobic conditions in the presence of fumarate and arsenate. Nitrate-grown cells exhibited the greatest level of cymA expression in both wild-type strains. Lastly, site-directed mutagenesis of the first Cys to Ser in each of the four CXXCH c-heme binding motifs of the CN-32 CymA nearly eliminated growth on and reduction of arsenate. Together, these results indicate that the biochemical mechanism of arsenate respiration and reduction requires the interactions of ArrAB with a membrane-associated tetraheme cytochrome, which in the non-arsenate-respiring Shewanella species Shewanella oneidensis strain MR-1, has pleiotropic effects on Fe(III), Mn(IV), dimethyl sulfoxide, nitrate, nitrite, and fumarate respiration.