Alkanes are saturated apolar hydrocarbons that range from their simplest form, methane, to high-molecular-weight compounds. Although alkanes were once considered biologically recalcitrant under anaerobic conditions, microbiological investigations have now identified several microbial taxa that can anaerobically degrade alkanes. Here we review recent discoveries in the anaerobic oxidation of alkanes with a specific focus on archaea that use specific methyl coenzyme M reductases to activate their substrates. Our understanding of the diversity of uncultured alkane-oxidizing archaea has expanded through the use of environmental metagenomics and enrichment cultures of syntrophic methane-, ethane-, propane-, and butane-oxidizing marine archaea with sulfate-reducing bacteria. A recently cultured group of archaea directly couples long-chain alkane degradation with methane formation, expanding the range of substrates used for methanogenesis. This article summarizes the rapidly growing knowledge of the diversity, physiology, and habitat distribution of alkane-degrading archaea.