Microbial methane consumption in anoxic sediments significantly impacts the global environment by reducing the flux of greenhouse gases from ocean to atmosphere. Despite its significance, the biological mechanisms controlling anaerobic methane oxidation are not well characterized. One current model suggests that relatives of methane-producing Archaea developed the capacity to reverse methanogenesis and thereby to consume methane to produce cellular carbon and energy. We report here a test of the "reverse-methanogenesis" hypothesis by genomic analyses of methane-oxidizing Archaea from deep-sea sediments. Our results show that nearly all genes typically associated with methane production are present in one specific group of archaeal methanotrophs. These genome-based observations support previous hypotheses and provide an informed foundation for metabolic modeling of anaerobic methane oxidation.