A phosphate-solubilizing bacterial strain designated $PS38^T$ was isolated from farm soil. The isolate was a Gram-positive, motile, endospore-forming, rod-shaped bacterium. It grew optimally at $37^{circ}C$ and pH 7.5. The predominant cellular fatty acids were anteiso-$C_{15:0}$, anteiso-$C_{17:0}$, and iso-$C_{16:0}$. The DNA G+C content was 49.5 mol% and the predominant menaquinone was MK-7. Phylogenetic analyses based on 16S rRNA gene sequences showed that the strain $PS38^T$ belonged to the genus Paenibacillus and was most closely related to Paenibacillus chibensis JCM $9905^T$, P. barengoltzii SAFN-$016^T$, P. timonensis $2301032^T$, and P. motobuensis $MC10^T$ with 96.3%, 96.0%, 95.9%, and 95.5% 16S rRNA gene sequence similarity, respectively. On the basis of morphological, chemotaxonomic, physiological, and phylogenetic properties, strain $PS38^T$ represents a novel species of the genus Paenibacillus, for which the name Paenibacillus telluris sp. nov. is proposed. The type strain is $PS38^T$ (=KCTC $13946^T$ =CGMCC $1.10695^T$).