Surface mining of enormous oil sands deposits in northeastern Alberta, Canada since 1967 has contributed greatly to Canada's economy but has also received negative international attention due largely to environmental concerns and challenges. Not only have microbes profoundly affected the composition and behavior of this petroleum resource over geological time, they currently influence the management of semi-solid tailings in oil sands tailings ponds (OSTPs) and tailings reclamation. Historically, microbial impacts on OSTPs were generally discounted, but next-generation sequencing and biogeochemical studies have revealed unexpectedly diverse indigenous communities and expanded our fundamental understanding of anaerobic microbial functions. OSTPs that experienced different processing and management histories have developed distinct microbial communities that influence the behavior and reclamation of the tailings stored therein. In particular, the interactions of Deltaproteobacteria and Firmicutes with methanogenic archaea impact greenhouse gas emissions, sulfur cycling, pore water toxicity, sediment biogeochemistry and densification, water usage and the trajectory of long-term mine waste reclamation. This review summarizes historical data; synthesizes current understanding of microbial diversity and activities in situ and in vitro; predicts microbial effects on tailings remediation and reclamation; and highlights knowledge gaps for future research.