A psychrotolerant sulfate-reducing bacterium, designated B15(T), was isolated from supercooled water brine from within permafrost of the Varandey Peninsula, on the southern coast of the Barents Sea. Cells were Gram-negative, motile vibrions (3.0-4.0×0.4-0.5 µm) with a single polar flagellum. The isolate was positive for desulfoviridin as a bisulfite reductase. Strain B15(T) grew at -2 to 28 °C (optimum 24 °C) and with 0-2.0% NaCl (optimum 0.2%). The isolate used H(2) plus acetate, formate, ethanol, lactate, pyruvate and choline as electron donors and used sulfate, sulfite, thiosulfate, elemental sulfur, DMSO and Fe(3+) as electron acceptors. Pyruvate and lactate were not fermented in the absence of sulfate. The G+C content of genomic DNA was 55.2 mol%. Analysis of the 16S rRNA gene sequence showed that the isolate belonged to the genus Desulfovibrio. Its closest relatives were Desulfovibrio idahonensis CY1(T) (98.8% 16S rRNA gene sequence similarity) and Desulfovibrio mexicanus Lup1(T) (96.5%). On the basis of genotypic, phenotypic and phylogenetic characteristics, the isolate represents a novel species, for which the name Desulfovibrio arcticus sp. nov. is proposed; the type strain is B15(T) (=VKM B-2367(T)=DSM 21064(T)).