The in situ degradation of the two nitramine explosives, hexahydro-1,3,5-trinitro-1,3,5-triazine (RDX) and octahydro-1,3,5,7-tetranitro-1,3,5,7-tetrazocine (HMX), was evaluated using a mixture of RDX and HMX, incubated anaerobically at 10 °C with marine sediment from a previous military dumping site of unexploded ordnance (UXO) in Halifax Harbor, Nova Scotia, Canada. The RDX concentration (14.7 mg·L–1) in the aqueous phase was reduced by half in 4 days, while reduction of HMX concentration (1.2 mg·L–1) by half required 50 days. Supplementation with the carbon sources glucose, acetate, or citrate did not affect the removal rate of RDX but improved removal of HMX. Optimal mineralization of RDX and HMX was obtained in the presence of glucose. Using universally labeled (UL)-[14C]RDX, we obtained a carbon mass balance distributed as follows: CO2, 48%–58%; water soluble products, 27%–31%; acetonitrile extractable products, 2.0%–3.4%; and products covalently bound to the sediments and biomass, 8.9% (in the presence of glucose). The disappearance of RDX was accompanied by the formation of the mononitroso derivative hexahydro-1-nitroso-3,5-dinitro-1,3,5-triazine (MNX) and formaldehyde (HCHO) that subsequently disappeared. In the case of HMX, mineralization reached only 13%–27% after 115 days of incubation in the presence or absence of the carbon sources. The disappearance of HMX was also accompanied by the formation of the mononitroso derivative. The total population of psychrotrophic anaerobes that grew at 10 °C was 2.6 × 103 colony-forming units·(g sediment dry mass)–1, and some psychrotrophic sediment isolates were capable of degrading RDX under conditions similar to those used for sediments. Based on the distribution of products, we suggest that the sediment microorganisms degrade RDX and HMX via an initial reduction to the corresponding mononitroso derivative, followed by denitration and ring cleavage.