Two bacterial strains, MC-246^T and MC-247, were isolated from municipal urban waste compost and characterized by a polyphasic approach. Both isolates were Gram-stain-variable, endospore-forming rods that were catalase-, oxidase- and β-galactosidase-positive, and able to grow at 25–50 °C and pH 7.0–9.0, with optimum growth at 37 °C and pH 7. The predominant cellular fatty acids were anteiso-C_{15 : 0}, iso-C_{15 : 0}, iso-C_{16 : 0}, anteiso-C_{17 : 0} and iso-C_{17 : 0}; the major respiratory quinone was menaquinone MK-7; the cell wall peptidoglycan was of type A1γ; and the DNA G+C content was 49 mol%. These characteristics, as well as data from 16S RNA gene sequence analysis, showed that these strains were affiliated with the genus Paenibacillus; the type strains of Paenibacillus ginsengarvi and Paenibacillus hodogayensis were among their closest neighbours (<94.2 % sequence similarity). Nevertheless, the hypothesis that strains MC-246^T and MC-247 could represent a novel species was supported by the low 16S rRNA gene sequence similarity values shared with other members of the genus Paenibacillus and by the observation of distinct biochemical and physiological traits. Strains MC-246^T and MC-247 shared 99.6 % 16S rRNA gene sequence similarity and showed almost identical MALDI-TOF mass spectra, but could be distinguished at the phenotypic and genotypic level. However, DNA–DNA hybridization between strains MC-246^T and MC-247 resulted in values above 70 % indicating that both organisms represent a single species, for which the name Paenibacillus residui sp. nov. is proposed; the type strain is MC-246^T (=DSM 22072^T =CCUG 57263^T).