Tailoring of semiconducting metal oxide nanostructures, which possess controlled pore size and concentration, is of great value to accurately detect various volatile organic compounds in exhaled breath, which act as potential biomarkers for many health conditions. In this work, we have developed a very simple and robust route for controlling both the size and distribution of spherical pores in electrospun WO3 nanofibers (NFs) via a sacrificial templating route using polystyrene colloids with different diameters (200 nm and 500 nm). A tentacle-like structure with randomly distributed pores on the surface of electrospun WO3 NFs were achieved, which exhibited improved surface area as well as porosity. Porous WO3 NFs with enhanced surface area exhibited high gas response (Rair/Rgas = 43.1 at 5 ppm) towards small and light H2S molecules. In contrast, porous WO3 NFs with maximized pore diameter showed a high response (Rair/Rgas = 2.8 at 5 ppm) towards large and heavy acetone molecules. Further enhanced sensing performance (Rair/Rgas = 65.6 at 5 ppm H2S) was achieved by functionalizing porous WO3 NFs with 0.1 wt% non-oxidized graphene (NOGR) flakes by forming a Schottky barrier (ΔΦ = 0.11) at the junction between the WO3 NFs (Φ = 4.56 eV) and NOGR flakes (Φ = 4.67 eV), which showed high potential for the diagnosis of halitosis.