In this work, core-shell WO3-SnO2 (CS-WS) nanofibers (NFs) have been successfully synthesized via a coaxial electrospinning approach. The structure and morphology characteristics of the resultant products were investigated by X-ray diffraction (XRD), scanning electron microscopy (SEM), transmission electron microscopy (TEM), and X-ray photoelectron spectra (XPS). To investigate the sensing mechanism of the CS-WS NFs, sensors based on SnO2 NFs, WO3 NFs, and SnO2-WO3 composite NFs were fabricated respectively, and their gas sensing properties were investigated by using CO, ethanol, toluene, acetone, and ammonia as the test gas. The results indicated that the CS-WS NFs exhibited a good response to ethanol (5.09 at 10 ppm) and short response/recovery time (18.5 s and 282 s) compared with the other test gases. The enhanced ethanol sensing properties of CS-WS NFs compared with those of SnO2 NFs were closely associated with the CS structure and its derivative effect due to the different work function of SnO2 and WO3. The approach proposed in this study may contribute to the realization of more sensitive metal oxide semiconductor (MOS) core-shell heterostructure sensors.