STOCKHOLDERS' AGREEMENT

Exhibit 10.4

Stockholders’ Agreement

Natural Gas Services Group, Inc.
2911 South County Road 1260
Midland, Texas 79706

Gentlemen:

     Natural Gas Services Group, Inc. (“ NGSG “), a Colorado corporation, is issuing an aggregate of 609,756 shares of its common stock, par value $.01 per share (the “ Restricted Securities ”), to Paul Hensley, Jim Hazlett and Tony Vohjesus (collectively, the “ Sellers ” and each individually, a “Seller”) as partial consideration for NGSG’s purchase (the “ Purchase ”) of all of the issued and outstanding shares of capital stock of Screw Compression Systems, Inc., a Texas corporation, from Sellers pursuant to the Stock Purchase Agreement, dated as of October 18, 2004, 2004, as amended by Amendment No. 1 to Stock Purchase Agreement, dated as of December 6, 2004 (the “ Purchase Agreement ”). The undersigned understands that the issuance is being made pursuant to exemptions from the registration requirements of the Securities Act of 1933, as amended (the “ Securities Act ”), and pursuant to exemptions from the registration and other requirements of applicable state securities laws. In order to induce NGSG to consummate the Purchase, Sellers have executed and delivered this Stockholders’ Agreement (this “ Agreement ”) to NGSG.

1. Representations, Warranties and Covenants of Each Seller . Each Seller, severally and not jointly, hereby represents, warrants and covenants to NGSG as follows:

     a. Such Seller is acquiring the Restricted Securities for his own account for investment purposes only, and not with a view to, or for resale in connection with, any distribution other than in compliance with the registration requirements under the Securities Act or the securities laws of any state or pursuant to an exemption therefrom.

     b. Such Seller understands that (A) the Restricted Securities (1) have not been registered under the Securities Act or any state securities laws, (2) will be issued in reliance upon an exemption from the registration and prospectus delivery requirements of the Securities Act and state securities laws for an offer and sale of securities not involving a public offering which relate to private purchases and (3) may not be sold, transferred or otherwise disposed of without satisfaction of certain conditions, including registration under, or the availability of an exemption from registration under, the Securities Act and applicable state securities laws, and (B) such Seller must therefore bear the economic risk of such investment indefinitely unless a subsequent disposition thereof is registered under the Securities Act and applicable state securities laws or is exempt therefrom. Such Seller further understands that such exemptions depend upon, among other things, the nature of the investment intent of the undersigned expressed herein.

     c. Such Seller has been furnished by NGSG all information (or provided access to all information) regarding the business and financial condition of NGSG, the attributes of the Restricted Securities and the merits and risks of an investment in the Restricted Securities which such Seller has requested to evaluate an investment in the Restricted Securities. Specifically, the undersigned acknowledges that such Seller has had an opportunity to review NGSG ‘s Annual Report on Form 10-KSB for the year ended December 31, 2003 and Quarterly Reports on Form 10-QSB for the fiscal quarters ended March 31, 2004, June 30, 2004 and September 30, 2004 and the other SEC Documents (as defined in the Purchase Agreement).

     d. Such Seller is an “accredited investor” as defined in Rule 501 of Regulation D promulgated under the Securities Act, and he, or those persons retained by him, has knowledge, skill and experience in financial, business and investment matters relating to an investment of the same nature as the Restricted Securities and is capable of evaluating the merits and risks of such investment and protecting himself in connection with the Purchase and an investment in the Restricted Securities. Such Seller has, to the extent deemed necessary by him retained, at his own expense, and relied upon, appropriate professional advice regarding the investment, tax and legal merits and consequences of an investment in the Restricted Securities. Such Seller has examined the SEC Documents, or caused the same to be examined, by his representatives to the extent he deems necessary or appropriate. Such Seller has not received any legal, business, tax or other advice from NGSG, its counsel or other representatives.

     e. Such Seller acknowledges that (i) it has been called to his attention that his investment in the Restricted Securities involves risk and (ii) he understands that the Restricted Securities to be issued in the Purchase will be an illiquid investment, subject to any future registration pursuant to this Agreement.

     f. No person or entity, other than NGSG, has been authorized to give any information or to make any representations on behalf of NGSG in connection with the Purchase, and, if given or made, such information or representations have not been relied upon by such Seller as having been made or authorized by NGSG. The only representations, warranties and information made by NGSG in connection with the Purchase are those contained in the Purchase Agreement and the SEC Documents.

     g. NGSG has provided such Seller the opportunity to ask questions of, and receive answers from, NGSG concerning the Purchase and the Restricted Securities and to obtain any appropriate additional information necessary to the investment decision being made by him in connection with the Purchase and the Restricted Securities.

     h. Such Seller acknowledges that he has been advised that:

     IN MAKING AN INVESTMENT DECISION REGARDING THE RESTRICTED SECURITIES, HE MUST RELY ON HIS OWN EXAMINATION OF NGSG AND THE TERMS OF THE PURCHASE, INCLUDING THE MERITS AND RISKS INVOLVED.

THE RESTRICTED SECURITIES HAVE NOT BEEN RECOMMENDED BY ANY FEDERAL OR STATE SECURITIES COMMISSION OR REGULATORY AUTHORITY.

     THE RESTRICTED SECURITIES ARE SUBJECT TO RESTRICTIONS ON TRANSFERABILITY AND RESALE, AND MAY NOT BE TRANSFERRED OR RESOLD EXCEPT AS PERMITTED UNDER THE SECURITIES ACT OF 1933, AS AMENDED, AND APPLICABLE STATE SECURITIES LAWS, PURSUANT TO REGISTRATION OR EXEMPTION THEREFROM. THE SECURITIES ARE ALSO SUBJECT TO ADDITIONAL RESTRICTIONS ON TRANSFERABILITY SET FORTH IN THIS AGREEMENT.

     The foregoing representations and warranties and undertakings are made by and on behalf of each Seller with the intent that they be relied upon by NGSG in determining each Seller’s suitability as an investor. Each Seller hereby agrees that such representations and warranties shall survive his purchase of the Restricted Securities.

2. Standstill . Unless waived in writing by NGSG from time to time, during the period commencing on the Closing Date and ending on the third anniversary thereof, neither Sellers nor any of their respective affiliates (as defined in Rule 12b-2 under the Securities Exchange Act of 1934, as amended) will:

     (a) acquire or agree, offer, seek or propose to acquire (or request permission to do so), ownership (including, but not limited to, beneficial ownership as defined in Rule 13d-3 under the Securities Exchange Act of 1934, as amended) of any assets or businesses or any additional securities issued by NGSG, or any rights or options to acquire such ownership (including from a third party), or

     (b) contest any election of directors by the stockholders of NGSG, or

     (c) otherwise act, alone or in concert with others, to induce or attempt to induce any other person to initiate any stockholder proposal or a tender offer for any voting secutrites of NGSG, or

     (d) enter into any discussions, negotiations, arrangements or understandings with any third party with respect to any of the foregoing.

3. Restrictions on Transferability; Registration Rights .

     The Restricted Securities shall not be transferable except upon the conditions specified in this Section 3; provided that, notwithstanding any other provision of this Section 3, each Seller shall have the right to transfer any Restricted Securities upon the prior written consent of NGSG. Each transferee shall be subject to the same transfer restrictions imposed on Sellers by this Agreement. All rights and obligations of Sellers set forth in this Section 3 will inure to the benefit of and be binding upon any transferee of the Restricted Securities.

     3.1 Restrictive Legend . Unless and until otherwise permitted by this Section 3, each certificate for Restricted Securities issued under the Purchase Agreement, and each certificate for any Restricted Securities issued to any subsequent permitted transferee of any such certificate, shall be stamped or otherwise imprinted with a legend in substantially the following form:

     3.2 Notice of Proposed Transfers . Prior to any transfer or attempted transfer of any Restricted Securities (other than pursuant to Rule 144 under the Securities Act or registration of the Restricted Securities under the Securities Act), the Seller of such Restricted Securities shall give written notice to NGSG of such Seller’s intention to effect such transfer. Each such notice (i) shall describe the manner and circumstances of the proposed transfer in sufficient detail, and shall contain an undertaking by the Seller giving such notice to furnish such other information as may be required, to enable counsel to render the opinions referred to below, and (ii) shall designate the counsel for the Seller giving such notice. Such Seller shall obtain the services of counsel described below at his own expense. The Seller giving such notice shall submit a copy thereof to the counsel designated in such notice. If in the opinion of such counsel, which is reasonably satisfactory to NGSG, the proposed transfer of such Restricted Securities may be effected without registration of such Res