We report on the NO gas sensing properties of Al-doped zinc oxide-carbon nanotube (ZnO-CNT) wire-like layered composites fabricated by coaxially coating Al-doped ZnO thin films on randomly oriented single-walled carbon nanotubes. We were able to wrap thin ZnO layers around the CNTs using the pulsed laser deposition method, forming wire-like nanostructures of ZnO-CNT. Microstructural observations revealed an ultrathin wire-like structure with a diameter of several tens of nm. Gas sensors based on ZnO-CNT wire-like layered composites were found to exhibit a novel sensing capability that originated from the genuine characteristics of the composites. Specifically, it was observed by measured gas sensing characteristics that the gas sensors based on ZnO-CNT layered composites showed a very high sensitivity of above 1,500% for NO gas in dry air at an optimal operating temperature of $200^{circ}C$; the sensors also showed a low NO gas detection limit at a sub-ppm level in dry air. The enhanced gas sensing properties of the ZnO-CNT wire-like layered composites are ascribed to a catalytic effect of Al elements on the surface reaction and an increase in the effective surface reaction area of the active ZnO layer due to the coating of CNT templates with a higher surface-to-volume ratio structure. These results suggest that ZnO-CNT composites made of ultrathin Al-doped ZnO layers uniformly coated around carbon nanotubes can be promising materials for use in practical high-performance NO gas sensors.