A Rhodococcus sp. UKMP-5M isolate was shown to detoxify cyanide successfully, suggesting the presence of an intrinsic property in the bacterium which required no prior cyanide exposure for induction of this property. However, in order to promote growth, Rhodococcus sp. UKMP-5M was fully acclimatized to cyanide after 7 successive subcultures in 0.1 mM KCN for 30 days. To further shorten the lag phase and simultaneously increase the tolerance towards higher cyanide concentrations, the bacterium was induced with various nitrile compounds sharing a similar degradatory pathway to cyanide. Acetonitrile emerged as the most favored inducer and the induced cells were able to degrade 0.1 mM KCN almost completely within 18 h. With the addition of subsequent aliquots of 0.1 mM KCN a shorter period for complete removal of cyanide was required, which proved to be advantageous economically. Both resting cells and crude enzyme of Rhodococcus sp. UKMP-5M were able to biodegrade cyanide to ammonia and formate without the formation of formamide, implying the identification of a simple hydrolytic cyanide degradation pathway involving the enzyme cyanidase. Further verification with SDS-PAGE revealed that the molecular weight of the active enzyme was estimated to be 38 kDa, which is consistent with previously reported cyanidases. Since the recent advancement in the application of biological methods in treating cyanide-bearing wastewater has been promising, the discovery of this new bacterium will add value by diversifying the existing microbial populations capable of cyanide detoxification.