The aims of this study were to evaluate the biodegradability of tetracyanonickelate (II) [K2[Ni(CN)4] (TCN) by Klebsiella oxytoca under anaerobic conditions. Anaerobic serum bottles and fermenter experiments were conducted to evaluate the effects of nitrogen sources and pH on the TCN biodegradation potential by K. oxytoca. Results reveal that TCN can be biotransformed to methane by resting cells of K. oxytoca. Results show that TCN biodegradation was inhibited by the addition of nitrate, nitrite, or ammonia at higher concentrations (5 and 10 mM). Moreover, it was found that the optimum pH for TCN conversion by K. oxytoca was about 7.1. Results from the fermenter experiment show that TCN can be completely degraded within 14 days. K. oxytoca is capable of using TCN as the nitrogen source under anaerobic conditions. TCN could be biotransformed to non-toxic end product (methane) by resting cells of K. oxytoca. Higher TCN biodegradation rate can be obtained under alkaline conditions. This study provides us insight into the characteristics of TCN conversion by K. oxytoca under anaerobic conditions. These findings would be helpful in designing a practical system inoculated with K. oxytoca for the treatment of cyanide-containing wastewater.