Strain ML311-T8T was isolated from a glacial retreat area in Svalbard, Norway, and was taxonomically characterized by a polyphasic approach. Upon phylogenetic analysis, strain ML311-T8T was clustered with Paenibacillus arcticus MME2_ R6T and P. contaminans CKOBP-6T with 98.3–98.6 and 93.5– 93.9% 16S rRNA gene sequence similarities, respectively. DNA-DNA hybridization values between strain ML311-T8T and P. arcticus MME2_R6T was 19.9%. The genomic DNA G+C content was 41.1 mol%. The isolated strain was Gramstain- positive, strictly aerobic and rod-shaped, and grew in 0–0.5% (w/v) NaCl, at 4–23°C and pH 6.0–10.0, with optimal growth in 0% (w/v) NaCl, at 20°C and pH 7.0–8.0. The predominant respiratory quinone of strain ML311-T8T was MK- 7 and the major fatty acids were anteiso-C15:0 and C16:0. The polar lipids of strain ML311-T8T were phosphatidylglycerol, phosphatidylethanolamine, diphosphatidylglycerol, three unidentified amino lipids, and three unidentified lipids. On the basis of polyphasic taxonomic analysis, the strain ML311-T8T is proposed to represent a novel species of the genus Paenibacillus, for which the name Paenibacillus psychroresistens sp. nov. is proposed. The type strain is ML311-T8T (= KCCM 43190T = JCM 31243T).