A large fraction of globally produced methane is converted to CO2 by anaerobic oxidation in marine sediments. Strong geochemical evidence for net methane consumption in anoxic sediments is based on methane profiles, radiotracer experiments and stable carbon isotope data. But the elusive microorganisms mediating this reaction have not yet been isolated, and the pathway of anaerobic oxidation of methane is insufficiently understood. Recent data suggest that certain archaea reverse the process of methanogenesis by interaction with sulphate-reducing bacteria. Here we provide microscopic evidence for a structured consortium of archaea and sulphate-reducing bacteria, which we identified by fluorescence in situ hybridization using specific 16S rRNA-targeted oligonucleotide probes. In this example of a structured archaeal-bacterial symbiosis, the archaea grow in dense aggregates of about 100 cells and are surrounded by sulphate-reducing bacteria. These aggregates were abundant in gas-hydrate-rich sediments with extremely high rates of methane-based sulphate reduction, and apparently mediate anaerobic oxidation of methane.