The enzyme QueF catalyzes the reduction of the nitrile group of 7-cyano-7-deazaguanine (preQ(0)) to 7-aminomethyl-7-deazaguanine (preQ(1)), the only nitrile reduction reaction known in biology. We describe here two crystal structures of Bacillus subtilis QueF, one of the wild-type enzyme in complex with the substrate preQ(0), trapped as a covalent thioimide, a putative intermediate in the reaction, and the second of the C55A mutant in complex with the substrate preQ(0) bound noncovalently. The QueF enzyme forms an asymmetric tunnel-fold homodecamer of two head-to-head facing pentameric subunits, harboring 10 active sites at the intersubunit interfaces. In both structures, a preQ(0) molecule is bound at eight sites, and in the wild-type enzyme, it forms a thioimide covalent linkage to the catalytic residue Cys-55. Both structural and transient kinetic data show that preQ(0) binding, not thioimide formation, induces a large conformational change in and closure of the active site. Based on these data, we propose a mechanism for the activation of the Cys-55 nucleophile and subsequent hydride transfer.