The pollution with Cr (VI) in the environment is widespread mainly due to its uses in various industrial applications such as chrome plating, stainless steel, preparation of alloys and industrial water cooling. Although several studies have been conducted previously to evaluate the bioremediation of Cr(VI)-contaminated areas, very little is known regarding the role of microbial mats in this approach. The current study is based on the microbial mats naturally developed at three locations within an abandoned chromite mining site in Nakhal, Oman. The objectives of the study included investigating the removal of 1, 5, 15, 20 and 50 mg L-1 of Cr(VI) by microbial mats A, B and C under anaerobic conditions using spectrophotometry and inductively-coupled plasma optical emission spectroscopy (ICP-OES) and evaluating the associated shifts in the mat bacterial communities at the end of degradation using Illumina MiSeq. The degradation of different concentrations of Cr(VI) depended on the microbial composition of the mat and the Cr(VI) concentration itself. Mat A samples continued to show a rapid reduction in the Cr(VI) concentration until zero values were detected after 23 days. However, a complete removal of Cr(VI) by mats B and C were detected only after 29 days. Further investigation revealed that the same mat A required different incubation periods when Cr(VI) concentration was increased in the site water. The NMDS analysis of the MiSeq data obtained showed that microbial mats underwent distinct community shifts depending mainly on the Cr(VI) concentration and the inherent bacterial community of the mat. Mat A samples showed a clear shift in the bacterial community structure in favour of Clostridia at 1 mg L-1 Cr(VI) while when exposed to higher concentrations of Cr(VI), the bacterial community structure was altered in favour of Gammaproteobacteria, Bacilli and Alphaproteobacteria. Thus, microbial mats can serve as effective bioremediation agents for Cr(VI)-contaminated areas in the natural environment. Future research should focus on the isolation of potential Cr(VI)-degrading microbial strains that can perform decontamination even under anaerobic conditions. Future research should focus on the isolation of potential Cr(VI)-degrading microbial strains that can perform decontamination even under anaerobic conditions.