© The Author(s), 2012. This article is distributed under the terms of the Creative Commons Attribution License. The definitive version was published in PLoS ONE 7 (2012): e42872, doi:10.1371/journal.pone.0042872. ; The seafloor is a unique environment, which allows insights into how geochemical processes affect the diversity of biological life. Among its diverse ecosystems are deep-sea brine pools - water bodies characterized by a unique combination of extreme conditions. The ‘polyextremophiles’ that constitute the microbial assemblage of these deep hot brines have not been comprehensively studied. We report a comparative taxonomic analysis of the prokaryotic communities of the sediments directly below the Red Sea brine pools, namely, Atlantis II, Discovery, Chain Deep, and an adjacent brine-influenced site. Analyses of sediment samples and high-throughput pyrosequencing of PCR-amplified environmental 16S ribosomal RNA genes (16S rDNA) revealed that one sulfur (S)-rich Atlantis II and one nitrogen (N)-rich Discovery Deep section contained distinct microbial populations that differed from those found in the other sediment samples examined. Proteobacteria, Actinobacteria, Cyanobacteria, Deferribacteres, and Euryarchaeota were the most abundant bacterial and archaeal phyla in both the S- and N-rich sections. Relative abundance-based hierarchical clustering of the 16S rDNA pyrotags assigned to major taxonomic groups allowed us to categorize the archaeal and bacterial communities into three major and distinct groups; group I was unique to the S-rich Atlantis II section (ATII-1), group II was characteristic for the N-rich Discovery sample (DD-1), and group III reflected the composition of the remaining sediments. Many of the groups detected in the S-rich Atlantis II section are likely to play a dominant role in the cycling of methane and sulfur due to their phylogenetic affiliations with bacteria and archaea involved in anaerobic methane oxidation and sulfate reduction. ; This work was supported by King Abdullah University for Science and Technology Global Collaborative Partners (GCR) program.