Low-cost, low power consumption gas sensors that can detect or quantify various gas analytes are of increasing interest for various applications ranging from mobile health, to environmental exposure assessment and homeland security. In particular miniature gas sensors based on nanomaterials that can be manufactured in the form of sensor arrays present great potential for the development of portable monitoring devices. In this study, we demonstrate that a chemiresistive nanosensor comprised of single walled carbon nanotubes decorated with gold nanoparticles has impressive sensitivity to elemental mercury (Hg) gas concentrations, with a lower detection limit as low as 2 ppb(v). Furthermore, this nanosensor was found to regenerate, though slowly, without any additional recovery steps. Finally, the mercury vapor sensing mechanism allowed for direct investigations into the origin of Surface Enhanced Raman Scattering (SERS) in carbon nanotubes decorated with Au nanoparticles.