Nitroglycerin (glyceryl trinitrate, GTN), originally manufactured by Alfred Nobel, has been used to treat angina and heart failure for over 130 years. However, the molecular mechanism of GTN biotransformation has remained a mystery and it is not well understood why “tolerance” (i.e., loss of clinical efficacy) manifests over time. Here we purify a nitrate reductase that specifically catalyzes the formation of 1,2-glyceryl dinitrate and nitrite from GTN, leading to production of cGMP and relaxation of vascular smooth muscle both in vitro and in vivo, and we identify it as mitochondrial aldehyde dehydrogenase (mtALDH). We also show that mtALDH is inhibited in blood vessels made tolerant by GTN. These results demonstrate that the biotransformation of GTN occurs predominantly in mitochondria through a novel reductase action of mtALDH and suggest that nitrite is an obligate intermediate in generation of NO bioactivity. The data also indicate that attenuated biotransformation of GTN by mtALDH underlies the induction of nitrate tolerance. More generally, our studies provide new insights into subcellular processing of NO metabolites and suggest new approaches to generating NO bioactivity and overcoming nitrate tolerance.