Microbial diversity in the sediments of the Kara Sea shelf and the southern Yenisei Bay, differing in pore water mineralization, was studied using massive parallel pyrosequencing according to the 454 (Roche) technology. Members of the same phyla (Cyanobacteria, Verrucomicrobia, Actinobacteria, Proteobacteria, and Bacteroidetes) predominated in bacterial communities of the sediments, while their ratio and taxonomic composition varied within the phyla and depended on pore water mineralization. Increasing salinity gradient was found to coincide with increased share of the γ-Proteobacteria and decreased abundance of α- and β-Proteo- bacteria, as well as of the phyla Verrucomicrobia, Chloroflexi, Chlorobi, and Acidobacteria. Archaeal diversity was lower, with Thaumarchaeota predominant in the sediments with high and low mineralization, while Crenarchaeota predominated in moderately mineralized sediments. Microbial communities of the Kara Sea shelf and Yenisei Gulf sediments were found to contain the organisms capable of utilization of a broad spectrum of carbon sources, including gaseous and petroleum hydrocarbons.