Massive microbial mats covering up to 4-meter-high carbonate buildups prosper at methane seeps in anoxic waters of the northwestern Black Sea shelf. Strong 13C depletions indicate an incorporation of methane carbon into carbonates, bulk biomass, and specific lipids. The mats mainly consist of densely aggregated archaea (phylogenetic ANME-1 cluster) and sulfate-reducing bacteria (Desulfosarcina/Desulfococcus group). If incubated in vitro, these mats perform anaerobic oxidation of methane coupled to sulfate reduction. Obviously, anaerobic microbial consortia can generate both carbonate precipitation and substantial biomass accumulation, which has implications for our understanding of carbon cycling during earlier periods of Earth's history.