Graphene-based, flexible NO(2) sensors on paper substrates exhibited an immediate response (32-39%) once exposed to 200 ppm NO(2) gas under a strain of 0.5%. Chemical vapor deposition-grown graphene with a supporting poly(methyl methacrylate) layer was transferred onto paper substrates, followed by formation of two electrodes using silver paste. Current-voltage characteristics and dynamic sensing response were obtained under both relaxed and strained conditions. We demonstrate a facile method without complex photo-lithography and high vacuum processes for fabricating graphene-based flexible NO(2) sensors on paper substrates with high sensing response.