Hypersaline anoxic habitats harbour numerous novel uncultured archaea whose metabolic and ecological roles remain to be elucidated. Until recently, it was believed that energy generation via dissimilatory reduction of sulfur compounds is not functional at salt saturation conditions. Recent discovery of the strictly anaerobic acetotrophic Halanaeroarchaeum compels to change both this assumption and the traditional view on haloarchaea as aerobic heterotrophs. Here we report on isolation and characterization of a novel group of strictly anaerobic lithoheterotrophic haloarchaea, which we propose to classify as a new genus Halodesulfurarchaeum. Members of this previously unknown physiological group are capable of utilising formate or hydrogen as electron donors and elemental sulfur, thiosulfate or dimethylsulfoxide as electron acceptors. Using genome-wide proteomic analysis we have detected the full set of enzymes required for anaerobic respiration and analysed their substrate-specific expression. Such advanced metabolic plasticity and type of respiration, never seen before in haloarchaea, empower the wide distribution of Halodesulfurarchaeum in hypersaline inland lakes, solar salterns, lagoons and deep submarine anoxic brines. The discovery of this novel functional group of sulfur-respiring haloarchaea strengthens the evidence of their possible role in biogeochemical sulfur cycling linked to the terminal anaerobic carbon mineralisation in so far overlooked hypersaline anoxic habitats.