Two (per)chlorate-reducing bacteria, strains CUZ and NSS, were isolated from marine sediments in Berkeley and San Diego, CA, respectively. Strain CUZ respired both perchlorate and chlorate [collectively designated (per)chlorate], while strain NSS respired only chlorate. Phylogenetic analysis classified both strains as close relatives of the gammaproteobacterium Sedimenticola selenatireducens. Transmission electron microscopy (TEM) and scanning electron microscopy (SEM) preparations showed the presence of rod-shaped, motile cells containing one polar flagellum. Optimum growth for strain CUZ was observed at 25 to 30 °C, pH 7, and 4% NaCl, while strain NSS grew optimally at 37 to 42 °C, pH 7.5 to 8, and 1.5 to 2.5% NaCl. Both strains oxidized hydrogen, sulfide, various organic acids, and aromatics, such as benzoate and phenylacetate, as electron donors coupled to oxygen, nitrate, and (per)chlorate or chlorate as electron acceptors. The draft genome of strain CUZ carried the requisite (per)chlorate reduction island (PRI) for (per)chlorate respiration, while that of strain NSS carried the composite chlorate reduction transposon responsible for chlorate metabolism. The PRI of strain CUZ encoded a perchlorate reductase (Pcr), which reduced both perchlorate and chlorate, while the genome of strain NSS included a gene for a distinct chlorate reductase (Clr) that reduced only chlorate. When both (per)chlorate and nitrate were present, (per)chlorate was preferentially utilized if the inoculum was pregrown on (per)chlorate. Historically, (per)chlorate-reducing bacteria (PRB) and chlorate-reducing bacteria (CRB) have been isolated primarily from freshwater, mesophilic environments. This study describes the isolation and characterization of two highly related marine halophiles, one a PRB and the other a CRB, and thus broadens the known phylogenetic and physiological diversity of these unusual metabolisms.