Indigenous bacteria found in the sediment of the Emerald Basin (depth of 215 m, Atlantic Ocean) located offshore of Halifax Harbour (Nova Scotia, Canada) were previously found to be able to degrade the explosive compound hexahydro-1,3,5-trinitro-1,3,5-triazine (RDX). In the present study, a novel obligately respiratory, denitrifying and RDX-mineralizing bacterium, designated strain HAW-EB4T, was isolated from the marine sediment. This bacterium utilized peptone, yeast extract, Casamino acids, esters (Tweens 20, 40 and 80), sugars (N-acetyl-d-glucosamine, ribose), several C2 and C3 acids (acetate, pyruvate, lactate, propionate) and amino acids (serine, proline) as sole carbon and energy sources. Aerobically grown cells (in marine broth 2216 at 10 °C) contained C14 : 0 (6 %), iso-C15 : 0 (12 %), C16 : 0 (20 %), C16 : 1ω7 (37 %), C18 : 1ω7 (7 %) and C20 : 5ω3 (7 %) as major membrane fatty acids, and Q7 (28·1 %) and MK-7 (60·9 %) as dominant respiratory quinones, consistent with deep-sea species of Shewanella. The novel bacterium had a DNA G+C content of 45 mol% and showed similarity to Shewanella species in terms of 16S rRNA and gyrB gene sequences (93–99 and 67·3–88·4 % similarity, respectively), with Shewanella pealeana being the most closely related species. Genomic DNA–DNA hybridization between strain HAW-EB4T and S. pealeana revealed a level of relatedness of 17·9 %, lower than the 70 % species cut-off value, indicating that strain HAW-EB4T (=NCIMB 14093T=DSM 17350T) is the type strain of a novel species of Shewanella, for which the name Shewanella halifaxensis sp. nov. is proposed.