Azotobacter vinelandii, a strict aerobic nitrogen-fixing bacterium, has been extensively studied with regard to the ability of N2-fixation due to its high expression of nitrogenase and fast growth. Because nitrogenase can also reduce cyanide to ammonia and methane, cyanide degradation by A. vinelandii has been studied for the application in the bioremediation of cyanide-contaminated wastewater. Cyanide degradation by A. vinelandii in NFS (nitrogen-free sucrose) medium was examined in terms of cell growth and cyanide reduction, and the results were applied for cyanide-contaminated cassava mill wastewater. From the NFS medium study in the 300 ml flask, it was found that A. vinelandii in the early stationary growth phase could reduce cyanide more rapidly than the cells in the exponential growth phase, and 84.4% of cyanide was degraded in 66 h incubation upon addition of 3.0 mM of NaCN. The resting cells of A. vinelandii could also reduce cyanide concentration by 90.4% with 3.0 mM of NaCN in the large-scale (3 L) fermentation with the same incubation time. Finally, the optimized conditions were applied to the cassava mill wastewater bioremediation, and A. vinelandii was able to reduce the cyanide concentration by 69.7% after 66 h in the cassava mill wastewater containing 4.0 mM of NaCN in the 3 L fermenter. Related to cyanide degradation in the cassava mill wastewater, nitrogenase was the responsible enzyme, which was confirmed by methane production. These findings would be helpful to design a practical bioremediation system for the treatment of cyanide-contaminated wastewater.