The methyl-coenzyme M reductase (Mcr) enables archaea to produce and oxidize methane, critically impacting the global greenhouse gas budget. Recently cultured archaea activate short- and long-chain n-alkanes with divergent Mcr variants, termed alkyl-coenzyme M reductases (Acrs). Here, we probed the anaerobic oxidation of mid-chain petroleum alkanes at 70°C using oil-rich sediments from the Guaymas Basin. Incubations with alkanes from pentane to tetradecane produced active cultures. In these cultures, archaea of the genus Candidatus Alkanophaga activate the alkanes with Acrs and completely oxidize the alkyl groups to CO2. Ca. Alkanophaga form a deep-branching sister clade to the methanotrophs ANME-1 and are closely related to the short-chain alkane oxidizers Ca. Syntrophoarchaeum. This suggests that multi-carbon alkane metabolism preceded methane metabolism in the class Syntrophoarchaeia. Ca. Alkanophaga shuttle the electrons from alkane oxidation to sulfate-reducing Thermodesulfobacteria. The two partners form consortia that are potential key players in petroleum degradation in heated oil reservoirs.