Sensing of gas molecules is critical to environmental monitoring, control of chemical processes, agricultural, and medical applications. In particular, the detection of industrial toxic gases such as CO, NO_x, and NH₃ is very important for many industries. Metal oxides have been widely studied for the sensitivity of their properties to gases even though they do have some limitations. Recently, graphene has been considered as a promising material for gas sensing since its electronic properties are strongly affected by the adsorption of foreign molecules. Intrinsic graphene has high sensitivity at low gas concentrations; but the sensor selectivity is poor which limits its use in many practical applications. Hence, hybrid architectures formed by blending of nanoparticles of metal–oxides with graphene or its derivatives have been explored by several researchers which showed improved gas sensing ability, especially the sensitivity and selectivity at room temperature. Here we review the state of the art of gas sensors based on graphene and metal oxide hybrid nanostructures for detection of various common toxic gases.