Endospore-forming bacteria were isolated from insect-pathogenic nematodes, Heterorhabditis spp., from three diverse geographical locations. Spindle-shaped sporangia of these bacteria adhere to the free-living infective stage of the nematode, which carries them to new insect hosts, where the bacterium reproduces. These isolates were characterized based on phenotypic and chemotaxonomic properties and 16S rRNA gene sequences. Analysis of the 16S rRNA gene placed the isolates within the genus Paenibacillus. The isolates shared higher sequence similarities with each other (95.1-100%) than they did with any other named species within the genus (89.2-94%). Paenibacillus macquariensis, Paenibacillus azoreducens, Paenibacillus amylolyticus and Paenibacillus durus were among the species with highest sequence similarity to these isolates. The isolates shared a high degree of phenotypic similarity and were easily distinguished from closely related members of the genus. Anteiso-C15:0 and C16:0 were among the major fatty acid types and the DNA G + C content was approximately 44 mol% in all isolates. DNA-DNA similarity studies revealed genomic heterogeneity among the isolates, such that they are likely to represent more than one species. Two of the isolates (both from a Heterorhabditis megidis isolate from Estonia) are phenotypically distinguishable from the others and are proposed as a single species, Paenibacillus nematophilus sp. nov. The type strain for this novel species is NEM1aT (=DSM 13559T =NCIMB 13845T). The other isolates, although closely related to the proposed species, are likely to represent at least one, but most likely two, novel species.