Anaerobic microorganisms are thought to play a critical role in regulating the flux of short-chain gaseous alkanes (SCGAs; including ethane, propane and butane) from terrestrial and aquatic ecosystems to the atmosphere. Sulfate has been confirmed to act as electron acceptor supporting microbial anaerobic oxidation of SCGAs, yet several other energetically more favourable acceptors co-exist with these gases in anaerobic environments. Here, we show that a bioreactor seeded with biomass from a wastewater treatment facility can perform anaerobic propane oxidation coupled to nitrate reduction to dinitrogen gas and ammonium. The bioreactor was operated for more than 1000 days, and we used C- and N-labelling experiments, metagenomic, metatranscriptomic, metaproteomic and metabolite analyses to characterize the microbial community and the metabolic processes. The data collectively suggest that a species representing a novel order within the bacterial class Symbiobacteriia is responsible for the observed nitrate-dependent propane oxidation. The closed genome of this organism, which we designate as 'Candidatus Alkanivorans nitratireducens', encodes pathways for oxidation of propane to CO via fumarate addition, and for nitrate reduction, with all the key genes expressed during nitrate-dependent propane oxidation. Our results suggest that nitrate is a relevant electron sink for SCGA oxidation in anaerobic environments, constituting a new microbially-mediated link between the carbon and nitrogen cycles.