There is a current need to develop low-cost strategies to degrade and eliminate industrially used colorants discharged into the environment. Colorants discharged into natural water streams pose various threats, including: toxicity, degradation of aesthetics and inhibiting sunlight penetration into aquatic ecosystems. Dyes and colorants usually have complex aromatic molecular structures, which make them very stable and difficult to degrade and eliminate by conventional water treatment systems. The results in this work demonstrated that heavy metal-resistant Rhodotorula mucilaginosa strain UANL-001L isolated from the northeast region of Mexico produce an exopolysaccharide (EPS), during growth, which has colorant adsorption potential. The EPS produced was purified by precipitation and dialysis and was then physically and chemically characterized by Scanning Electron Microscopy, Fourier Transform Infrared Spectroscopy, and chemical elemental analysis. Here, the ability of the purified EPS produced to adsorb methylene blue (MB), which served as a model colorant, is studied. MB adsorption by the EPS is found to follow Langmuir Adsorption Isotherm kinetics at 25°C. Further, by calculating the Langmuir constant the adsorption capabilities of the EPS produced by the Rhodotorula mucilaginosa strain UANL-001L is compared to that of other adsorbents, both, microbially produced and from agroindustrial waste. The total adsorption capacity of the EPS, from the Rhodotorula mucilaginosa strain UANL-001L, was found to be two-fold greater than the best bioadsorbents reported in the literature. Finally, apart from determining which heavy metals stimulated EPS production in the strain, the optimal conditions of pH, heavy metal concentration, and rate of agitation of the growing culture for EPS production, was determined. The EPS reported here has the potential of aiding in the efficient removal of colorants both in water treatment plants and in situ in natural water streams.