To meet requirements in air quality monitoring, sensors are required that can measure the concentration of gaseous pollutants at concentrations down to the ppb and ppt levels, while at the same time they exhibiting high sensitivity, selectivity, and short response/recovery times. Among the different sensor types, those employing metal oxide semiconductors (MOSs) offer great promises as they can be manufactured in easy/inexpensive ways, and designed to measure the concentration of a wide range of target gases. MOS sensors rely on the adsorption of target gas molecules on the surface of the sensing material and the consequent capturing of electrons from the conduction band that in turn affects their conductivity. Despite their simplicity and ease of manufacturing, MOS gas sensors are restricted by high limits of detection (LOD; which are typically in the ppm range) as well as poor sensitivity and selectivity. LOD and sensitivity can in principle be addressed by nanostructuring the MOSs, thereby increasing their porosity and surface-to-volume ratio, whereas selectivity can be tailored through their chemical composition. In this paper we provide a critical review of the available techniques for nanostructuring MOSs using chemiresistive materials, and discuss how these can be used to attribute desired properties to the end gas sensors. We start by describing the operating principles of chemiresistive sensors, and key material properties that define their performance. The main part of the paper focuses on the available methods for synthesizing nanostructured MOSs for use in gas sensors. We close by addressing the current needs and provide perspectives for improving sensor performance in ways that can fulfill requirements for air quality monitoring. Graphical abstract: [Figure not available: see fulltext.].