In the last two decades, GaN nanostructures of various forms like nanowires (NWs), nanotubes (NTs), nanofibers (NFs), nanoparticles (NPs) and nanonetworks (NNs) have been reported for gas sensing applications. In this paper, we have reviewed our group’s work and the works published by other groups on the advances in GaN nanostructures-based sensors for detection of gases such as hydrogen (H2), alcohols (R-OH), methane (CH4), benzene and its derivatives, nitric oxide (NO), nitrogen dioxide (NO2), sulfur-dioxide (SO2), ammonia (NH3), hydrogen sulfide (H2S) and carbon dioxide (CO2). The important sensing performance parameters like limit of detection, response/recovery time and operating temperature for different type of sensors have been summarized and tabulated to provide a thorough performance comparison. A novel metric, the product of response time and limit of detection, has been established, to quantify and compare the overall sensing performance of GaN nanostructure-based devices reported so far. According to this metric, it was found that the InGaN/GaN NW-based sensor exhibits superior overall sensing performance for H2 gas sensing, whereas the GaN/(TiO2–Pt) nanowire-nanoclusters (NWNCs)-based sensor is better for ethanol sensing. The GaN/TiO2 NWNC-based sensor is also well suited for TNT sensing. This paper has also reviewed density-functional theory (DFT)-based first principle studies on the interaction between gas molecules and GaN. The implementation of machine learning algorithms on GaN nanostructured sensors and sensor array has been analyzed as well. Finally, gas sensing mechanism on GaN nanostructure-based sensors at room temperature has been discussed.