We report a highly sensitive NO2 gas sensor based on multi-layer graphene (MLG) films synthesized by a chemical vapor deposition method on a microheater-embedded flexible substrate. The MLG could detect low-concentration NO2 even at sub-ppm (<200 ppb) levels. It also exhibited a high resistance change of ~6% when it was exposed to 1 ppm NO2 gas at room temperature for 1 min. The exceptionally high sensitivity could be attributed to the large number of NO2 molecule adsorption sites on the MLG due to its a large surface area and various defect-sites, and to the high mobility of carriers transferred between the MLG films and the adsorbed gas molecules. Although desorption of the NO2 molecules was slow, it could be enhanced by an additional annealing process using an embedded Au microheater. The outstanding mechanical flexibility of the graphene film ensures the stable sensing response of the device under extreme bending stress. Our large-scale and easily reproducible MLG films can provide a proof-of-concept for future flexible NO2 gas sensor devices.