In addition to its role as a toxic environmental contaminant, cyanide has been hypothesized to play a key role in prebiotic chemistry and early biogeochemical evolution. While cyanide-hydrolyzing enzymes have been studied and engineered for bioremediation, the extant diversity of these enzymes remains underexplored. Additionally, the age and evolution of microbial cyanide metabolisms is poorly constrained. Here we provide comprehensive phylogenetic and molecular clock analyses of the distribution and evolution of the Class I nitrilases, thiocyanate hydrolases, and nitrile hydratases. Molecular clock analyses indicate that bacterial cyanide-reducing nitrilases were present by the Paleo- to Mesoproterozoic, and were subsequently horizontally transferred into eukaryotes. These results present a broad diversity of microbial enzymes that could be optimized for cyanide bioremediation.