Oil sands tailings ponds contain a variety of anaerobic microbes, including methanogens, sulfate- and nitrate-reducing bacteria. Methanogenic activity in samples from a tailings pond and its input streams was higher with trimethylamine (TMA) than with acetate. Methanogens closely affiliated to Methanomethylovorans hollandica were found in the TMA enrichments. Tailings sedimentation increased with methanogenic activity, irrespective whether TMA or acetate was used to stimulate methanogenesis. Increased sedimentation of autoclaved tailings was observed with added pure cultures under methanogenic, as well as under nitrate-reducing conditions, but not under sulfate-reducing conditions. Scanning electron microscopy and energy-dispersive X-ray spectroscopy indicated the presence of microbes and of extracellular polymeric substances in tailings particle aggregates, especially under methanogenic and nitrate-reducing conditions. Hence different classes of microorganisms growing in tailings ponds contribute to increased tailings aggregation and sedimentation. Because addition of nitrate is known to lower methane production by methanogenic consortia, these observations offer the potential to combine lower methane emissions with improved microbially-induced tailings sedimentation.