Seven strains of Gram-positive microorganisms capable of forming endospores have been isolated from soils of the region of potassium salt mining (Berezniki, Perm krai) by the method of enrichment cultures. Their typing by means of REP- and BOX-PCR has shown that four strains—I23 (= VKM V-2504), I26 (= VKM V-2505), I27, and I28—are of the same genogroup (type I), while strains SN501 (= VKM V-2508), I10b (= VKM V-2507), and I12b (= VKM V-2506) represent three different genogroups (types II, III, and IV, respectively). A phylogenetic analysis of 16S rRNA gene sequences has shown that strains I10b and SN501 belong to the genus Paenibacillus, and the remaining strains, to the genus Bacillus. These bacteria are tolerant of high salinity and alkalinity: they can grow at pH 7.0–9.0 and NaCl content of 90–110 g/l in the culture medium. They are also capable of utilizing diesel fuel and individual aromatic and aliphatic hydrocarbons.