The deep ocean and its sediments are a continuous source of non-methane short-chain alkanes (SCAs) including ethane, propane, and butane. Their high global warming potential, and contribution to local carbon and sulfur budgets has drawn significant scientific attention. Importantly, microbes can use gaseous alkanes and oxidize them to CO2, thus acting as effective biofilters. A relative decrease of these gases with a concomitant 13C enrichment of propane and n-butane in interstitial waters vs. the source suggests microbial anaerobic oxidation. The reported uncoupling of sulfate-reduction (SR) from anaerobic methane oxidation supports their microbial consumption. To date, strain BuS5 isolated from the sediments of Guaymas Basin, Gulf of California, is the only pure culture that can anaerobically degrade propane and n-butane. This organism belongs to a metabolically diverse cluster within the Deltaproteobacteria called Desulfosarcina/Desulfococcus. Other phylotypes involved in gaseous alkane degradation were identified based on stable-isotope labeling and fluorescence in-situ hybridization. A novel syntrophic association of the archaeal genus, Candidatus Syntrophoarchaeum, and a thermophilic SR bacterium, HotSeep-1 was recently discovered from the Guaymas basin, Gulf of California that can anaerobically oxidize n-butane. Strikingly, metagenomic data and the draft genomes of ca. Syntrophoarchaeum suggest that this organism uses a novel mechanism for n-butane oxidation, distinct from the well-established fumarate addition mechanism. These recent findings indicate that a lot remains to be understood about our understanding of anaerobic SCA degradation. This mini-review summarizes our current understanding of microbial anaerobic SCA degradation, and provides an outlook for future research.