The genus Natronospira is represented by a single species of extremely salt-tolerant aerobic alkaliphilic proteolytic bacterium, isolated from hypersaline soda lakes. When cells of Gram-positive cocci were used as a substrate instead of proteins at extremely haloalkaline conditions, two new members of this genus were enriched and isolated in pure culture from the same sites. Strains AB-CW1 and AB-CW4 are obligate aerobic heterotrophic proteolytic bacteria able to feed on both live and dead cells of staphylococci and a range of proteins and peptides. Similar to the type species, N. proteinivora, the isolates are extremely salt-tolerant obligate alkaliphiles. However, N. proteinivora was unable to use bacterial cells as a substrate. Electron microscopy showed direct contact between the prey and predator cells. Functional analysis of the AB-CW1 and AB-CW4 genomes identified two sets of genes coding for extracellular enzymes potentially involved in the predation and proteolysis, respectively. The first set includes several copies of lysozyme-like GH23 peptidoglycan-lyase and murein-specific M23 [Zn]-di-peptidase enabling the cell wall degradation. The second set features multiple copies of secreted serine and metallopeptidases apparently allowing for the strong proteolytic phenotype. Phylogenomic analysis placed the isolates into the genus Natronospira as two novel species members, and furthermore indicated that this genus forms a deep-branching lineage of a new family (Natronospiraceae) and order (Natronospirales) within the class Gammaproteobacteria. On the basis of distinct phenotypic and genomic properties, strain AB-CW1T (JCM 335396 = UQM 41579) is proposed to be classified as Natronospira elongata sp. nov., and AB-CW4T (JCM 335397 = UQM 41580) as Natronospira bacteriovora sp. nov.