EXHIBIT 23.1

Consent of Independent Registered Public Accounting Firm

The Board of Directors

Natural Gas Services Group, Inc.

Midland, Texas

We consent to the incorporation by reference in the registration statements on Form S-8 (No. 333-147311, No. 333-110954, No. 333-160068, No. 333-160063 and No. 333-153874) and the registration statements (No. 333-119502, No. 333-122687 and No. 333-161346) on Form S-3, of Natural Gas Services Group, Inc. of our report dated March 4, 2010, relating to our audits of the financial statements and internal control over financial reporting, which appear in this Annual Report on Form 10-K of Natural Gas Services Group, Inc for the year ended December 31, 2009.

/s/ HEIN & ASSOCIATES LLP

Dallas, Texas

March 4, 2010