The NO gas sensing properties of ZnO-carbon nanotube (ZnO-CNT) composites fabricated by the coaxial coating of single-walled CNTs with ZnO were investigated using pulsed laser deposition. Upon examination, the morphology and crystallinity of the ZnO-CNT composites showed that CNTs were uniformly coated with polycrystalline ZnO with a grain size as small as 5-10 nm. Gas sensing measurements clearly indicated a remarkable enhancement of the sensitivity of ZnO-CNT composites for NO gas compared to that of ZnO films while maintaining the strong sensing stability of the composites, properties that CNT-based sensing materials do not have. The enhanced gas sensing properties of the ZnO-CNT composites are attributed to an increase in the surface adsorption area of the ZnO layer via the coating by CNTs of a high surface-to-volume ratio structure. These results suggest that the ZnO-CNT composite is a promising template for novel solid-state semiconducting gas sensors.