Micrococcus lactis and Zhihengliuella aestuarii were described independently in 2011. Their type strains showed high levels of 16S rRNA gene sequence similarity (99.3%). Phylogenetic analysis revealed that M. lactis MCC 2278T and Z. aestuarii JCM 16166T formed a monophyletic group and showed distant relationships to other members of closely related genera such as Micrococcus, Zhihengliuella, Arthrobacter and Citricoccus. The presence of large proportions of iso-C14:0 and iso-C16:0 with small amounts of iso-C15:0 distinguished M. lactis MCC 2278T and Z. aestuarii JCM 16166T from other members of the genera Micrococcus and Zhihengliuella. Unlike other members of the genera Zhihengliuella and Micrococcus, M. lactis MCC 2278T and Z. aestuarii JCM 16166T showed growth at low concentrations of NaCl. Thus, based on distinctive phylogenetic, chemotaxonomic and physiological features of these two organisms in comparison with other members of the genera Micrococcus and Zhihengliuella, it is clear that they do not fit within the existing classification and deserve separate status. DNA-DNA hybridization between the two type strains was 63%, indicating that they represent separate species. In this study, we propose the creation of a novel genus, Neomicrococcus gen. nov., to accommodate the two species with Neomicrococcus aestuarii gen. nov., comb. nov. (type strain JCM 16166T = KCTC 19557T) as the type species. Neomicrococcus lactis comb. nov. (type strain MCC 2278T = DSM 23694T) is also proposed.