The enzyme QueF was recently identified as an enzyme involved in the biosynthesis of queuosine, a 7-deazaguanosine modified nucleoside found in bacterial and eukaryotic tRNA. QueF exhibits sequence homology to the type I GTP cyclohydrolases characterized by FolE, but contrary to the predictions based on sequence analysis the enzyme in fact catalyzes a mechanistically unrelated reaction, the NADPH-dependent reduction of 7-cyano-7-deazaguanine (preQ0) to 7-aminomethyl-7-deazaguanine (preQ1), a late step in the queuosine pathway. The reduction of a nitrile is unprecedented in biology, and we report here characterization and mechanistic studies of the enzyme from Bacillus subtilis. The recombinant enzyme exhibits optimal activity at pH 7.5 and moderate ionic strength, and is not dependent on metal ions for catalytic activity. Steady-state kinetic analysis provided a kcat = 0.66 +/- 0.04 min-1, KM (preQ0) = 0.237 +/- 0.045 microM, and KM (NADPH) = 19.2 +/- 1.1 microM. Based on sequence analysis and homology modeling we predicted previously that Cys55 would be present in the active site and in proximity to the nitrile group of preQ0. Consistent with that prediction we observed that the enzyme was inactivated when preincubated with iodoacetamide, and protected from inactivation when preQ0 was present. Furthermore, titrations of the enzyme with preQ0 in the absence of NADPH were accompanied by the appearance of a new absorption band at 376 nm in the UV-vis spectrum consistent with the formation of an alpha,beta-unsaturated thioimide. Site-directed mutagenesis of Cys55 to Ala or Ser resulted in loss of catalytic activity and no absorption at 376 nm upon addition of preQ0. Based on our data we propose a chemical mechanism for the enzyme-catalyzed reaction, and a chemical rationale for the observation of covalent catalysis.