Nitriles are uncommon in nature and are typically constructed from oximes via the oxidative decarboxylation of amino acid substrates or from the derivatization of carboxylic acids. Here we report a third strategy of nitrile biosynthesis featuring the cyanobacterial nitrile synthase AetD. During the biosynthesis of the 'eagle-killing' neurotoxin, aetokthonotoxin, AetD converts the alanyl side chain of 5,7-dibromo-L-tryptophan to a nitrile. Employing a combination of structural, biochemical, and biophysical techniques, we characterized AetD as a non-heme diiron enzyme that belongs to the emerging Heme Oxygenase-like Diiron Oxidase and Oxygenase (HDO) superfamily. High-resolution crystal structures of AetD together with the identification of catalytically relevant products provide mechanistic insights into how AetD affords this unique transformation that we propose proceeds via an aziridine intermediate. Our work presents a new paradigm for nitrile biogenesis and portrays a substrate binding and metallocofactor assembly mechanism that may be shared among other HDO enzymes.