Because of its rare occurrence in modern sediments, as well as the difficulty in synthesizing it under low-temperature conditions in the laboratory, the origin of sedimentary dolomite has remained a long-standing enigma, often referred to as the “dolomite problem.” Recently, anaerobic microorganisms, such as sulfate-reducing bacteria and methanogens, have been recognized for mediating dolomite precipitation. However, the exact role of microorganisms in dolomite crystallization is still under debate and the possible involvement of anaerobic fermenting bacteria has not been studied. In this study, we characterized the effect of purified non-metabolizing biomass and bound extracellular polymeric substances (EPS) of a natural consortium of anaerobic microorganisms dominated by fermenting bacteria and sulfate-reducing bacteria on Ca-Mg carbonate precipitation. This natural consortium was enriched from sediments of Deep Springs Lake, California, where dolomite is still precipitating. Our data show that disordered dolomite, a precursor of some sedimentary stoichiometric ordered dolomite, can be precipitated in calcite-seeded Ca-Mg carbonate solutions containing purified non-metabolizing consortium biomass. Bound EPS extracted from the consortium culture were shown to be the active component that triggered the crystallization of disordered dolomite. Further experiments show that purified non-metabolizing biomass from pure cultures of both anaerobic fermenting and sulfate-reducing bacteria closely related to those organisms present in the consortium could also catalyze the precipitation of disordered dolomite. This study contributes to the understanding of the “dolomite problem” by revealing (1) the catalytic effect of bound EPS on Ca-Mg carbonate crystallization and (2) the possible involvement of anaerobic fermenting bacteria in sedimentary dolomite formation, which has not been reported previously.