Thiol dioxygenases are a subset of non-heme mononuclear iron oxygenases that catalyze the O(2)-dependent oxidation of thiol-bearing substrates to yield sulfinic acid products. Cysteine dioxygenase (CDO) and 3-mercaptopropionic acid (3MPA) dioxygenase (MDO) are the most extensively characterized members of this enzyme family. As with many non-heme mononuclear iron oxidase/oxygenases, CDO and MDO exhibit an obligate-ordered addition of organic substrate before dioxygen. As this substrate-gated O(2)-reactivity extends to the oxygen-surrogate, nitric oxide (NO), EPR spectroscopy has long been used to interrogate the [substrate:NO:enzyme] ternary complex. In principle, these studies can be extrapolated to provide information about transient iron-oxo intermediates produced during catalytic turnover with dioxygen. In this work, we demonstrate that cyanide mimics the native thiol-substrate in ordered-addition experiments with MDO cloned from Azotobacter vinelandii (AvMDO). Following treatment of the catalytically active Fe(II)-AvMDO with excess cyanide, addition of NO yields a low-spin (S = 1/2) (CN/NO)-Fe-complex. Continuous wave and pulsed X-band EPR characterization of this complex produced in wild-type and H157N variant AvMDO reveal multiple nuclear hyperfine features diagnostic of interactions within the first- and outer-coordination sphere of the enzymatic Fe-site. Spectroscopically validated computational models indicate simultaneous coordination of two cyanide ligands replaces the bidentate (thiol and carboxylate) coordination of 3MPA allowing for NO-binding at the catalytically relevant O(2)-binding site. This promiscuous substrate-gated reactivity of AvMDO with NO provides an instructive counterpoint to the high substrate-specificity exhibited by mammalian CDO for l-cysteine.