Surface mining for bitumen extraction results in production of tailings that are deposited into large ponds. Tailings in the ponds support diverse microbial communities capable of metabolizing organic compounds and producing biogenic gases (methane, CH4 and carbon dioxide, CO2). Because of low endogenous concentrations of bioavailable nitrogen (N), tailings ponds might be deficient in available N (NO3-/NH4+). This study examined the potential of N2-fixation mediated methanogenic degradation of citrate and petroleum hydrocarbons in oil sands tailings under N-depleted conditions. Anaerobic primary cultures were set up with available N or N-deficient medium under N2 headspace using mature fine tailings (MFT) and amended with citrate as a carbon source. Citrate was metabolized to CH4 under both N available and deficient conditions suggesting N2-fixation mediated degradation of citrate. Acetylene reduction assay and incorporation of 15N2 stable isotope into microbial biomass supported N2-fixation during citrate metabolism.