Aldoxime dehydratase (Oxd) catalyzes the dehydration of aldoximes (R–CH=N–OH) to their corresponding nitrile (R–C▪N). Oxd is a heme-containing enzyme that catalyzes the dehydration reaction as its physiological function. We have determined the first two structures of Oxd: the substrate-free OxdRE at 1.8 Å resolution and the n-butyraldoxime- and propionaldoxime-bound OxdREs at 1.8 and 1.6 Å resolutions, respectively. Unlike other heme enzymes, the organic substrate is directly bound to the heme iron in OxdRE. We determined the structure of the Michaelis complex of OxdRE by using the unique substrate binding and activity regulation properties of Oxd. The Michaelis complex was prepared by x-ray cryoradiolytic reduction of the ferric dead-end complex in which Oxd contains a Fe3+ heme form. The crystal structures reveal the mechanism of substrate recognition and the catalysis of OxdRE.