The temperature dependency of denitrification and anaerobic ammonium oxidation (anammox) rates from Arctic fjord sediments was investigated in a temperature gradient block incubator for temperatures ranging from −1 to 40°C. Community structure in intact sediments and slurry incubations was determined using Illumina SSU rRNA gene sequencing. The optimal temperature (Topt) for denitrification was 25–27°C, whereas anammox rates were optimal at 12–17°C. Both denitrification and anammox exhibited temperature responses consistent with a psychrophilic community, but anammox bacteria may be more specialized for psychrophilic activity. Long-term (1–2 months) warming experiments indicated that temperature increases of 5–10°C above in situ had little effect on the microbial community structure or the temperature response of denitrification and anammox. Increases of 25°C shifted denitrification temperature responses to mesophilic with concurrent community shifts, and anammox activity was eliminated above 25°C. Additions of low molecular weight organic substrates (acetate and lactate) caused increases in denitrification rates, corroborating the hypothesis that the supply of organic substrates is a more dominant control of respiration rates than low temperature. These results suggest that climate-related changes in sinking particulate flux will likely alter rates of N removal more rapidly than warming.