Four Gram-stain-positive, aerobic bacterial strains isolated from a pharmaceutical clean room (strain WS4616(T)), a dessert milk product (strain WS4617) and from raw milk (strains WS4623 and WS4624) were characterized using a polyphasic approach. Phylogenetic analyses based on 16S rRNA and recA gene sequences showed that they formed a distinct lineage within the family Propionibacteriaceae. Similarity values between 16S rRNA gene sequences of the four novel strains and the type species of all genera belonging to the family Propionibacteriaceae were 89.2-94.1%. The major cellular fatty acid was anteiso-C(15:0) and the major polar lipids were diphosphatidylglycerol and phosphatidylglycerol. Respiratory quinones were MK-8(H(4)) and MK-9(H(4)). The cell-wall peptidoglycan of type A3γ contained ll-diaminopimelic acid, alanine, glycine and glutamic acid. The G+C content of the genomic DNA of strain WS4616(T) was 67.7 mol%. The whole-cell sugar pattern contained ribose, mannose, arabinose, glucose and galactose. On the basis of phenotypic and genetic data, strains WS4616(T), WS4617, WS4623 and WS4624 are classified as members of a novel species in a new genus of the family Propionibacteriaceae, for which the name Naumannella halotolerans gen. nov., sp. nov. is proposed. The type strain is WS4616(T) ( = DSM 24323(T) = LMG 26184(T)) and three additional strains are WS4617, WS4623 and WS4624.