Nanostructured semiconducting metal oxides and particularly single nanowire devices offer exceptional gas sensitivity but at the expense of statistical variations and excessive noise levels. In this study TiO2/poly(vinyl acetate) composite nanofiber mats were directly electrospun onto interdigitated Pt electrode arrays, hot pressed at 120 degrees C, and calcined at 450 degrees C. This resulted in a novel multiple nanowire network composed of sheaths of 200-500 nm diameter cores filled with readily gas accessible approximately 10 nm thick single-crystal anatase fibrils. TiO2 nanofiber sensors tested for NO2, in dry air, exhibited exceptional sensitivity showing with, for example, a 833% increase in sensor resistance when exposed to 500 ppb NO2 at 300 degrees C, consistent with a detection limit estimated to be well below 1 ppb. Unusual response patterns were observed at high NO2 concentrations (> 12.5 ppm), consistent with n to p inversion of the surface-trap limited conduction facilitated by the high surface-to-volume ratio of this material.