We have investigated anaerobic respiration of the archaeal model organism Halobacterium sp. strain NRC-1 by using phenotypic and genetic analysis, bioinformatics, and transcriptome analysis. NRC-1 was found to grow on either dimethyl sulfoxide (DMSO) or trimethylamine N-oxide (TMAO) as the sole terminal electron acceptor, with a doubling time of 1 day. An operon, dmsREABCD, encoding a putative regulatory protein, DmsR, a molybdopterin oxidoreductase of the DMSO reductase family (DmsEABC), and a molecular chaperone (DmsD) was identified by bioinformatics and confirmed as a transcriptional unit by reverse transcriptase PCR analysis. dmsR, dmsA, and dmsD in-frame deletion mutants were individually constructed. Phenotypic analysis demonstrated that dmsR, dmsA, and dmsD are required for anaerobic respiration on DMSO and TMAO. The requirement for dmsR, whose predicted product contains a DNA-binding domain similar to that of the Bat family of activators (COG3413), indicated that it functions as an activator. A cysteine-rich domain was found in the dmsR gene, which may be involved in oxygen sensing. Microarray analysis using a whole-genome 60-mer oligonucleotide array showed that the dms operon is induced during anaerobic respiration. Comparison of dmsR+ and DeltadmsR strains by use of microarrays showed that the induction of the dmsEABCD operon is dependent on a functional dmsR gene, consistent with its action as a transcriptional activator. Our results clearly establish the genes required for anaerobic respiration using DMSO and TMAO in an archaeon for the first time.