Exceptionally sensitive hydrogen sensors were produced using Pd-nanoparticle-decorated, single vanadium dioxide nanowires. The high-sensitivity arises from the large downward shift in the insulator to metal transition temperature following the adsorption on and incorporation of atomic hydrogen, produced by dissociative chemisorption on Pd, in the VO2, producing 1000-fold current increases. During a rapid initial process, the insulator to metal transition temperature is decreased by >10 °C even when exposed to trace amounts of hydrogen gas. Subsequently, hydrogen continues to diffuse into the VO2 for several hours before saturation is achieved with only a modest change in the insulator to metal transition temperature but with a significant increase in the conductivity. The two time scales over which H-related processes occur in VO2 likely signal the involvement of two distinct mechanisms influencing the electronic structure of the material one of which involves electron−phonon coupling pursuant to the modification of the vibrational normal modes of the solid by the introduction of H as an impurity.