A cellulolytic bacterial strain, designated P118, isolated from the gut of the tropical fish Parotocinclus maculicauda was identified as belonging to the genus Paenibacillus based on phenotypic and chemotaxonomic characteristics and the 16S rRNA gene sequence. The novel strain was Gram-positive, spore-forming and rod-shaped. Catalase but not oxidase was produced. Carboxymethylcellulose was hydrolyzed but starch or gelatin was not. Acetoin production was negative whereas nitrate reduction and urease production were positive. Many carbohydrates served as carbon sources for growth. MK-7 was the predominant isoprenoid quinone. Anteiso-C 15:0 (38.73%) and C 16:0 (20.85%) were the dominant cellular fatty acids. Strain P118 was closely related to Paenibacillus amylolyticus NRRL NRS-290, P. pabuli HSCC 492, P. tundrae Ab10b, P. xylanexedens B22a, and P. tylopili MK2 with 98.3-98.8% 16S rRNA gene sequence similarity. The results presented here suggest that strain P118 represents a novel species of the genus Paenibacillus and it is a potential strain for further studies concerning its role in the production of industrially important products from cellulosic biomass.