Halobacteria (henceforth: Haloarchaea) are predominantly aerobic halophiles that are thought to have evolved from anaerobic methanogens. This remarkable transformation most likely involved an extensive influx of bacterial genes. Whether it entailed a single massive transfer event or a gradual stream of transfers remains a matter of debate. To address this, genomes that descend from methanogen-to-halophile intermediates are necessary. Here, we present five such near-complete genomes of Marine Group IV archaea (Hikarchaeia), the closest known relatives of Haloarchaea. Their inclusion in gene tree-aware ancestral reconstructions reveals an intermediate stage that had already lost a large number of genes, including nearly all of those involved in methanogenesis and the Wood-Ljungdahl pathway. In contrast, the last Haloarchaea common ancestor gained a large number of genes and expanded its aerobic respiration and salt/UV resistance gene repertoire. Our results suggest that complex and gradual patterns of gain and loss shaped the methanogen-to-halophile transition.