Large reservoirs of natural gas in the oceanic subsurface sustain complex communities of anaerobic microbes, including archaeal lineages with potential to mediate oxidation of hydrocarbons such as methane and butane. Here we describe a previously unknown archaeal phylum, Helarchaeota, belonging to the Asgard superphylum and with the potential for hydrocarbon oxidation. We reconstruct Helarchaeota genomes from metagenomic data derived from hydrothermal deep-sea sediments in the hydrocarbon-rich Guaymas Basin. The genomes encode methyl-CoM reductase-like enzymes that are similar to those found in butane-oxidizing archaea, as well as several enzymes potentially involved in alkyl-CoA oxidation and the Wood-Ljungdahl pathway. We suggest that members of the Helarchaeota have the potential to activate and subsequently anaerobically oxidize hydrothermally generated short-chain hydrocarbons.