A Gram-stain-positive, rod-shaped, non-endospore-forming, motile by means of peritrichous flagella, facultatively anaerobic bacterium designated TI45-13arT was isolated from Nuruk, a Korean traditional Makgeolli fermentation starter. It grew at 4–35°C (optimum, 28–30°C), pH 5.0–9.0 (optimum, pH 7.0) and NaCl concentrations up to 5% (w/v). Phylogenetic trees generated using 16S rRNA gene sequences revealed that strain TI45-13arT belonged to the genus Paenibacillus and showed the highest sequence similarities with Paenibacillus kyungheensis DCY88T (98.5%), Paenibacillus hordei RH-N24T (98.4%) and Paenibacillus nicotianae YIM h-19T (98.1%). The major fatty acid was anteiso-C15:0. The DNA G+C content was 39.0 mol%, and MK-7 was the predominant isoprenoid quinone. The polar lipids were diphosphatidylglycerol, phosphatidylglycerol, phosphatidylethanolamine, three unidentified glycolipids, and one unidentified aminoglycolipid. The cell-wall peptidoglycan contained meso-diaminopimelic acid. On the basis of polyphasic taxonomy study, it was suggested that strain TI45-13arT represents a novel species within the genus Paenibacillus for which the name Paenibacillus nuruki sp. nov. is proposed. The type strain was TI45-13arT (= KACC 18728T = NBRC 112013T).