Globally, 3 Gt of bauxite residue is currently in storage, with an additional 120 Mt generated every year. Bauxite residue is an alkaline, saline, sodic, massive, and fine grained material with little organic carbon or plant nutrients. To date, remediation of bauxite residue has focused on the use of chemical and physical amendments to address high pH, high salinity, and poor drainage and aeration. No studies to date have evaluated the potential for microbial communities to contribute to remediation as part of a combined approach integrating chemical, physical, and biological amendments. This review considers natural alkaline, saline environments that present similar challenges for microbial survival and evaluates candidate microorganisms that are both adapted for survival in these environments and have the capacity to carry out beneficial metabolisms in bauxite residue. Fermentation, sulfur oxidation, and extracellular polymeric substance production emerge as promising pathways for bioremediation whether employed individually or in combination. A combination of bioaugmentation (addition of inocula from other alkaline, saline environments) and biostimulation (addition of nutrients to promote microbial growth and activity) of the native community in bauxite residue is recommended as the approach most likely to be successful in promoting bioremediation of bauxite residue.