Two novel spore-forming, Gram-positive, mesophilic, heterotrophic bacteria representing two novel species were isolated from the Jet Propulsion Laboratory Spacecraft Assembly Facility (JPL-SAF) at Pasadena, CA, USA. The incidence of similar strains was examined by screening the growing collection of isolates ( approximately 400 strains) obtained from the JPL-SAF using species-specific PCR primer sets designed from the 16S rRNA gene sequences of strains SAFN-016(T) and SAFN-007(T). Phylogenetic analysis of 16S rRNA gene sequences placed these novel isolates within the genus Paenibacillus. Two strains, SAFN-016(T) and SAFN-125, shared 98 % 16S rRNA gene sequence similarity with Paenibacillus timonensis and 97 % similarity with Paenibacillus macerans. Strain SAFN-007(T) showed 95.2 % 16S rRNA gene sequence similarity with Paenibacillus kobensis, its nearest phylogenetic neighbour. The results of DNA-DNA hybridization, physiological tests and biochemical analysis allowed genotypic and phenotypic differentiation of the isolates from currently recognized Paenibacillus species. Strain SAFN-007(T) and strains SAFN-016(T) and SAFN-125 are representatives of two separate novel species, for which the names Paenibacillus pasadenensis sp. nov. (type strain SAFN-007(T)=ATCC BAA-1211(T)=NBRC 101214(T)) and Paenibacillus barengoltzii sp. nov. (type strain SAFN-016(T)=ATCC BAA-1209(T)=NBRC 101215(T)) are proposed.