A Gram-negative and obligately anaerobic marine bacterium, strain HAW-EB21T, was isolated in a previous study from marine sediment from the Atlantic Ocean, near Halifax Harbor, Canada, and found to have the potential to degrade both hexahydro-1,3,5-trinitro-1,3,5-triazine and octahydro-1,3,5,7-tetranitro-1,3,5,7-tetrazocine. In the present study, phylogenetic analyses showed that strain HAW-EB21T was only distantly related to the genera Propionigenium and Ilyobacter with 6.6–7.5 % and 8.2–10.5 % dissimilarity as measured by 16S rRNA and 23S rRNA gene sequence analyses, respectively. Strain HAW-EB21T displayed unique properties in being psychrotrophic (18.5 °C optimum) and unable to utilize any of the carbon substrates (succinate, l-tartrate, 3-hydroxybutyrate, quinate or shikimate) used for isolating members of the genera Propionigenium and Ilyobacter. Strain HAW-EB21T utilized glucose, fructose, maltose, N-acetyl-d-glucosamine, citrate, pyruvate, fumarate and Casitone as carbon sources and produced H2 and acetate as the major fermentation products. Cells grown at 10 °C produced C15 : 1 (30 %), C16 : 1 ω7 (15 %) and C16 : 0 (16 %) as major membrane fatty acids. The novel strain had a genomic DNA G+C content of 28.1 mol%, lower than the values of the genera Ilyobacter and Propionigenium. Based on the present results, the novel isolate is suggested to be a member of a new genus for which the name Psychrilyobacter atlanticus gen. nov., sp. nov. is proposed. The type strain of the type species is HAW-EB21T (=DSM 19335T=JCM 14977T).