The springs at Gypsum Hill and Colour Peak on Axel Heiberg Island in the Canadian Arctic originate from deep salt aquifers and are among the few known examples of cold springs in thick permafrost on Earth. The springs discharge cold anoxic brines (7.5 to 15.8% salts), with a mean oxidoreduction potential of -325 mV, and contain high concentrations of sulfate and sulfide. We surveyed the microbial diversity in the sediments of seven springs by denaturing gradient gel electrophoresis (DGGE) and analyzing clone libraries of 16S rRNA genes amplified with Bacteria and Archaea-specific primers. Dendrogram analysis of the DGGE banding patterns divided the springs into two clusters based on their geographic origin. Bacterial 16S rRNA clone sequences from the Gypsum Hill library (spring GH-4) were classified into seven phyla (Actinobacteria, Bacteroidetes, Firmicutes, Gemmatimonadetes, Proteobacteria, Spirochaetes, and Verrucomicrobia); Deltaproteobacteria and Gammaproteobacteria sequences represented half of the clone library. Sequences related to Proteobacteria (82%), Firmicutes (9%), and Bacteroidetes (6%) constituted 97% of the bacterial clone library from Colour Peak (spring CP-1). Most GH-4 archaeal clone sequences (79%) were related to the Crenarchaeota while half of the CP-1 sequences were related to orders Halobacteriales and Methanosarcinales of the Euryarchaeota. Sequences related to the sulfur-oxidizing bacterium Thiomicrospira psychrophila dominated both the GH-4 (19%) and CP-1 (45%) bacterial libraries, and 56 to 76% of the bacterial sequences were from potential sulfur-metabolizing bacteria. These results suggest that the utilization and cycling of sulfur compounds may play a major role in the energy production and maintenance of microbial communities in these unique, cold environments.