Marine sediments at ocean margins vent substantial amounts of methane(1,2). Microbial oxidation of the methane released can trigger the precipitation of carbonate within sediments and support a broad diversity of seafloor ecosystems(3,4). The factors controlling microbial activity and carbonate precipitation associated with the seepage of submarine fluid over geological time remain poorly constrained. Here, we characterize the petrology and geochemistry of rocks sampled from metre-size build-ups of methane-derived carbonate chimneys located at the Amon mud volcano on the Nile deep-sea fan. We find that these carbonates comprise porous structures composed of aggregated spherules of aragonite, and closely resemble microbial carbonate reefs forming at present in the anoxic bottom waters of the Black Sea(5). Using U-series dating, we show that the Amon carbonate build-ups formed between 12 and 7 thousand years ago, contemporaneous with the deposition of organic-rich sediments in the eastern Mediterranean, the so-called sapropel layer S1. We propose that the onset of deep-water suboxic or anoxic conditions associated with sapropel formation resulted in the development of intense anaerobic microbial activity at the sea floor, and thus the formation of carbonate chimneys.