Atomically thin sheets of carbon known as "graphene" have captured the imagination of much of the scientific world during the past few years. Although these single sheets of graphite were under our noses for years-within technologies ranging from the humble pencil, which has been around since at least 1565 (Petroski, H. The Pencil: A History of Design and Circumstance; Alfred A. Knopf: New York, 1993), to modern nuclear reactors-graphene was merely considered as part of graphite's crystal structure until 2004, when Novoselov, Geim, and colleagues (Science 2004, 306, 666-669) first presented some of the surprising electrical properties of graphene layers they had isolated by mechanically peeling sheets off graphite crystals. Today, graphene's unique electronic structures and properties, bolstered by other intriguing properties discovered in the intervening years, threaten the dominance of carbon nanotubes, a more mature allotrope of carbon, in potential applications from electronics to sensors. In this review, we will consider the promise of graphene for producing small-scale gas sensors for environmental monitoring.