Graphene is a two-dimensional material with a capability of gas sensing, which is here shown to be drastically improved by inducing gentle disorder in the lattice. We report that by using a focused ion beam technique, controlled disorder can be introduced into the graphene structure through Ga(+) ion irradiation. This disorder leads to an increase in the electrical response of graphene to NO(2) gas molecules by a factor of three in an ambient environment (air). Ab initio density functional calculations indicate that NO(2) molecules bind strongly to Stone-Wales defects, where they modify electronic states close to the Fermi level, which in turn influence the transport properties. The demonstrated gas sensor, utilizing structurally defected graphene, shows faster response, higher conductivity changes and thus higher sensitivity to NO(2) as compared to pristine graphene.