To determine the phylogenetic relationship among Paenibacillus species, putative replication origin regions were compared. In the rsmG-gyrA region, gene arrangements in Paenibacillus species were identical to those of Bacillus species, with the exception of an open reading frame (orf14) positioned between gyrB and gyrA, which was observed only in Paenibacillus species. The orf14 product was homologous to the endospore-associated proteins YheC and YheD of Bacillus subtilis. Phylogenetic analysis based on the YheCD proteins suggested that Orf14 could be categorized into the YheC group. In the Paenibacillus genome, DnaA box clusters were found in rpmH-dnaA and dnaA-dnaN intergenic regions, known as box regions C and R, respectively; this localization was similar to that observed in B. halodurans. A phylogenetic tree based on the nucleotide sequences of the whole replication origin regions suggested that P. popilliae, P. thiaminolyticus, and P. dendritiformis are closely related species.