A Gram-stain positive, facultative anaerobic endospore-forming bacterium, designated strain YIM h-19(T), was isolated from a tobacco sample. Cells were observed to be motile rods by means of peritrichous flagella and colonies were observed to be convex, yellow, circular and showed catalase-positive and oxidase-negative reactions. Strain YIM h-19(T) was able to grow at 4-45 °C, pH 6.0-8.0 and 0-3 % NaCl (w/v). The predominant respiratory quinone was identified as MK-7. Major fatty acids were identified as anteiso-C15:0, anteiso-C17:0 and C16:0. The polar lipids were found to be phosphatidylethanolamine, diphosphatidylglycerol, phosphatidylglycerol and two unidentified polar lipids. The genomic DNA G+C content was determined to be 54 mol%. 16S rRNA gene sequence analysis showed the strain YIM h-19(T) was most closely related to Paenibacillus hordei RH-N24(T) and Paenibacillus hunanensis FeL05(T) with similarities of 98.30 and 94.64 % respectively. However, DNA-DNA hybridization data indicated that the isolate represented a novel genomic species with the genus Paenibacillus. All data from genotypic and phenotypic analyses support the conclusion that strain YIM h-19(T) represents a novel species of the genus Paenibacillus, for which the name Paenibacillus nicotianae sp. nov. is proposed. The type strain is YIM h-19(T) (=CGMCC1.12819(T) = NRRL B-59112(T)).