Anaerobic oxidation of methane (AOM) in marine sediments is an important microbial process in the global carbon cycle and in control of greenhouse gas emission. The responsible organisms supposedly reverse the reactions of methanogenesis, but cultures providing biochemical proof of this have not been isolated. Here we searched for AOM-associated cell components in microbial mats from anoxic methane seeps in the Black Sea. These mats catalyse AOM rather than carry out methanogenesis. We extracted a prominent nickel compound displaying the same absorption spectrum as the nickel cofactor F430 of methyl-coenzyme M reductase, the terminal enzyme of methanogenesis; however, the nickel compound exhibited a higher molecular mass than F430. The apparent variant of F(430) was part of an abundant protein that was purified from the mat and that consists of three different subunits. Determined amino-terminal amino acid sequences matched a gene locus cloned from the mat. Sequence analyses revealed similarities to methyl-coenzyme M reductase from methanogenic archaea. The abundance of the nickel protein (7% of extracted proteins) in the mat suggests an important role in AOM.