The short-chain, non-methane hydrocarbons propane and butane can contribute significantly to the carbon and sulfur cycles in marine environments affected by oil or natural gas seepage. In the present study, we enriched and identified novel propane and butane-degrading sulfate reducers from marine oil and gas cold seeps in the Gulf of Mexico and Hydrate Ridge. The enrichment cultures obtained were able to degrade simultaneously propane and butane, but not other gaseous alkanes. They were cold-adapted, showing highest sulfate-reduction rates between 16 and 20 °C. Analysis of 16S rRNA gene libraries, followed by whole-cell hybridizations with sequence-specific oligonucleotide probes showed that each enrichment culture was dominated by a unique phylotype affiliated with the Desulfosarcina-Desulfococcus cluster within the Deltaproteobacteria. These phylotypes formed a distinct phylogenetic cluster of propane and butane degraders, including sequences from environments associated with hydrocarbon seeps. Incubations with ¹³C-labeled substrates, hybridizations with sequence-specific probes and nanoSIMS analyses showed that cells of the dominant phylotypes were the first to become enriched in ¹³C, demonstrating that they were directly involved in hydrocarbon degradation. Furthermore, using the nanoSIMS data, carbon assimilation rates were calculated for the dominant cells in each enrichment culture.