A novel Gram-positive, motile, endospore-forming, aerobic bacterium was isolated from the NASA Phoenix Lander assembly clean room that exhibits 100 % 16S rRNA gene sequence similarity to two strains isolated from a deep subsurface environment. All strains are rod-shaped, endospore-forming bacteria, whose endospores are resistant to UV radiation up to 500 J m⁻². A polyphasic taxonomic study including traditional phenotypic tests, fatty acid analysis, 16S rRNA gene sequencing and DNA–DNA hybridization analysis was performed to characterize these novel strains. The 16S rRNA gene sequencing convincingly grouped these novel strains within the genus Paenibacillus as a separate cluster from previously described species. The similarity of 16S rRNA gene sequences among the novel strains was identical but only 98.1 to 98.5 % with their nearest neighbours Paenibacillus barengoltzii ATCC BAA-1209^T and Paenibacillus timonensis CIP 108005^T. The menaquinone MK-7 was dominant in these novel strains as shown in other species of the genus Paenibacillus. The DNA–DNA hybridization dissociation value was <45 % with the closest related species. The novel strains had DNA G+C contents of 51.9 to 52.8 mol%. Phenotypically, the novel strains can be readily differentiated from closely related species by the absence of urease and gelatinase and the production of acids from a variety of sugars including l-arabinose. The major fatty acid was anteiso-C_{15 : 0} as seen in P. barengoltzii and P. timonensis whereas the proportion of C_{16 : 0} was significantly different from the closely related species. Based on phylogenetic and phenotypic results, it was concluded that these strains represent a novel species of the genus Paenibacillus, for which the name Paenibacillus phoenicis sp. nov. is proposed. The type strain is 3PO2SA^T ( = NRRL B-59348^T = NBRC 106274^T).