The taxonomic position of two Gram-positive strains, YIM 70084(T) and YIM 70097(T), isolated from hypersaline soils was determined by a polyphasic approach. Cells of strain YIM 70084(T) are motile cocci, whereas those of strain YIM 70097(T) are non-motile rods. The G+C contents of their DNA are 64.4 and 66.7 mol%. Both strains had chemotaxonomic markers typical of the genus Nesterenkonia and formed a coherent cluster with Nesterenkonia species in a phylogenetic inference based on 16S rDNA sequence analysis, exhibiting less than 97 % similarity to each other and to the other two type strains of the genus. Phylogenetic distinction and differences in the peptidoglycan type, composition of cell-wall sugars, phospholipid patterns, the major menaquinones and other phenotypic characteristics indicate that the strains under study represent two novel species, Nesterenkonia halotolerans sp. nov. (type strain YIM 70084(T)=CCTCC AA 001022(T)=DSM 15474(T)) and Nesterenkonia xinjiangensis sp. nov. (type strain YIM 70097(T)=CCTCC AA 001025(T)=DSM 15475(T)).