A novel bacterium, strain b11s-2T was isolated from Pu’er tea. The isolate was Gram-positive, endosporeforming motile rod that grew at 15~42°C and pH 6.0~10.2. The DNA G+C content was 48.3 mol%, the predominant isoprenoid quinone was MK-7, and the predominant cellular fatty acid was anteiso-C15:0 (54.2%) followed by C16:0 (15.5%) and iso-C16:0 (8.2%). The polar lipid pattern of b11s-2T was characterized by the presence of diphosphatidylglycerol, phosphatidylethanolamine, and phosphatidylglycerol. Phylogenetic analysis based on 16S rRNA gene sequence showed that the strain was affiliated within the Paenibacillaceae. The strain was most closely related to Paenibacillus granivorans A30T, with a similarity of 97.1%. Based on the phylogenetic and phenotypic characteristics of strain b11s-2T, the isolate is thought to represent a novel taxon in the genus Paenibacillus. The name Paenibacillus camelliae sp. nov. is proposed for the fermented tea isolate; the type strain is b11s-2T (= KCTC 13220T= CECT 7361T).