Sulfate reducing bacteria (SRB) have existed throughout much of Earth's history and remain major contributors to carbon cycling in modern systems. Despite their importance, misconceptions about SRB are prevalent. In particular, SRB are commonly thought to lack oxygen tolerance and to exist only in anoxic environments. Through the last two decades, researchers have discovered that SRB can, in fact, tolerate and even respire oxygen. Investigations of microbial mat systems have demonstrated that SRB are both abundant and active in the oxic zones of mats. Additionally, SRB have been found to be highly active in the lithified zones of microbial mats, suggesting a connection between sulfate reduction and mat lithification. In the present paper, we review recent research on SRB distribution and present new preliminary findings on both the diversity and distribution of δ-proteobacterial SRB in lithifying and non-lithifying microbial mat systems. These preliminary findings indicate the unexplored diversity of SRB in a microbial mat system and demonstrate the close microspatial association of SRB and cyanobacteria in the oxic zone of the mat. Possible mechanisms and further studies to elucidate mechanisms for carbonate precipitation via sulfate reduction are also discussed.