Anaerobic carboxydotrophy is a widespread catabolic trait in bacteria, with two dominant pathways: hydrogenogenic and acetogenic. The marginal mode by direct oxidation to CO2 using an external e-acceptor has only a few examples. Use of sulfidic sediments from two types of hypersaline lakes in anaerobic enrichments with CO as an e-donor and elemental sulfur as an e-acceptor led to isolation of two pure cultures of anaerobic carboxydotrophs belonging to two genera of sulfur-reducing haloarchaea: Halanaeroarchaeum sp. HSR-CO from salt lakes and Halalkaliarchaeum sp. AArc-CO from soda lakes. Anaerobic growth of extremely halophilic archaea with CO was obligatory depended on the presence of elemental sulfur as the electron acceptor and yeast extract as the carbon source. CO served as a direct electron donor and H2 was not generated from CO when cells were incubated with or without sulfur. The genomes of the isolates encode a catalytic Ni,Fe-CODH subunit CooS (distantly related to bacterial homologs) and its Ni-incorporating chaperone CooC (related to methanogenic homologs) within a single genomic locus. Similar loci were also present in a genome of the type species of Halalkaliarchaeum closely related to AArc-CO, and the ability for anaerobic sulfur-dependent carboxydotrophy was confirmed for three different strains of this genus. Moreover, similar proteins are encoded in three of the four genomes of recently described carbohydrate-utilizing sulfur-reducing haloarchaea belonging to the genus Halapricum and in two yet undescribed haloarchaeal species. Overall, this work demonstrated for the first time the potential for anaerobic sulfur-dependent carboxydotrophy in extremely halophilic archaea.