Hierarchical Co3O4@NiMoO4 core-shell nanowires (NWs) were synthesized utilizing a two-step hydrothermal method. The NWs show a high chemiresistive response (at a temperature of 255 °C) to xylene, with an Rgas/Rair ratio of 24.6 at 100 ppm xylene, while the response towards toluene, benzene, ethanol, and acetone, CO, H2S and NO2 is much weaker. In contrast, pure Co3O4 nanowires exhibit weak responses to all the vapors/gases and poor selectivity. The new NW sensor displays an almost linear response (1–100 ppm) to xylene and a lower detection limit of 424 ppb. The remarkable gas sensing characteristics are attributed to the synergistic catalytic effect and the formation of a heterostructure between Co3O4 and NiMoO4.