Gold extraction by cyanidation generates toxic effluents stored in tailing dams which are an environmental hazard due to the presence of metal-cyanide complexes and sulfates. We aimed to isolate a native bacterial consortium from a gold mine tailing dam and study its cyanide biodegradation potential as part of tertiary biotechnological treatment. The cyanide-degrading consortium was streaked by serial dilutions on specific medium R2A. MALDI-TOF MS proteomic fingerprint of the isolates showed that bacterial strains belonged to Microbacterium paraoxydans, Brevibacterium casei, Brevundimonas vesicularis, Bacillus cereus, and Cellulosimicrobium cellulans. The first four genera were previously identified as cyanide degrading bacteria. Microbacterium, Brevibacterium. and Bacillus cereus were previously found in alkaline conditions. The five genera were also previously reported as resistant to several heavy metals. Cellulosimicrobium was previously described as cyanogenic, and, to our knowledge, this would be the first report to relate it also to cyanide biodegradation. These genera were identified as functional bacteria for cyanide degradation and might be suitable for mine tailing biotechnological tertiary treatment.