Endospore-forming bacteria were recovered from individual packages from different processing lines in a dairy plant during a tenacious periodical contamination of their UHT-milk production. Two colony types were seen, one of which was identified as Bacillus sporothermodurans. Analysis of the 16S rRNA gene of the second colony type placed these isolates within the genus Paenibacillus, with Paenibacillus lautus as the closest known relative. Moreover, over 99 % similarity was observed to the 16S rDNA sequence of MB 2035, a strain isolated previously from raw milk during a survey at dairy farms for very heat-resistant spore-forming bacteria. Nine other potentially closely related strains among the dairy farm isolates were found using rep-PCR typing. The taxonomic positions of these 19 isolates were further investigated using 16S rRNA gene sequencing and DNA-DNA hybridizations of representative strains. All 19 isolates shared a high degree of phenotypic similarity and were easily distinguished from closely related members of the genus. Anteiso-C(15 : 0), C(16 : 0) and iso-C(15 : 0) were among the major fatty acids and the genomic DNA G+C content was 51.6-51.7 mol%. Therefore, based on their phenotypic, phylogenetic and genomic distinctiveness, these 19 strains, isolated from both raw and heat-treated milk, are placed in the genus Paenibacillus as Paenibacillus lactis sp. nov. The type strain is MB 1871(T) (=LMG 21940(T)=DSM 15596(T)).