UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

SCHEDULE 13D

Under the Securities Exchange Act of 1934

(Amendment No. 2)*

Natural Gas Services Group, Inc.

(Name of Issuer)

Common Stock, par value $0.01 per share

(Title of Class of Securities)

63886Q109

(CUSIP Number)

Mill Road Capital III, L.P.

Attn: Thomas E. Lynch

382 Greenwich Avenue

Suite One

Greenwich, CT 06830

203-987-3500

With a copy to:

Peter M. Rosenblum, Esq.

Foley Hoag LLP

155 Seaport Blvd.

Boston, MA 02210

617-832-1151

(Name, Address and Telephone Number of Person Authorized to Receive Notices and Communications)

March 10, 2023

(Date of Event which Requires Filing of this Statement)

If the filing person has previously filed a statement on Schedule 13G to report the acquisition that is the subject of this Schedule 13D, and is filing this schedule because of §§240.13d-1(e), 240.13d-1(f) or 240.13d-1(g), check the following box.  ☐

Note: Schedules filed in paper format shall include a signed original and five copies of the schedule, including all exhibits. See §240.13d-7 for other parties to whom copies are sent.

The information required on the remainder of this cover page shall not be deemed to be “filed” for the purpose of Section 18 of the Securities Exchange Act of 1934 (“Act”) or otherwise subject to the liabilities of that section of the Act but shall be subject to all other provisions of the Act (however, see the Notes).

This Amendment No. 2 to the joint statement on Schedule 13D with respect to the common stock, par value $0.01 per share (the “Common Stock”), of Natural Gas Services Group, Inc., a Colorado corporation (the “Issuer”), filed by the Reporting Persons (as defined below) on January 4, 2021, as amended by Amendment No. 1 on Schedule 13D with respect to the Common Stock filed by the Reporting Persons on December 23, 2022 (such joint statement, as so amended and as amended herein, the “Schedule 13D”), amends the Schedule 13D as follows:

1. Item 4 of the Schedule 13D shall hereby be amended by inserting the following new paragraphs after the second paragraph:

On March 10, 2023, the Fund sent the letter attached hereto as Exhibit 3, which is incorporated herein by reference, to the Issuer setting forth its intention to nominate two directors for election at the Issuer’s 2023 Annual Meeting of Shareholders (the “Annual Meeting”) and serving as a notice of nomination in accordance with the Issuer’s bylaws and Rule 14a-19(b) under the Securities Exchange Act of 1934, as amended. The Fund requested in the letter that the Issuer name Justin C. Jacobs and Donald J. Tringali in its proxy statement as nominees for election to the Issuer’s board of directors at the Annual Meeting.

The Fund entered into a Nomination Agreement with Mr. Tringali on March 10, 2023, a copy of which is attached hereto as Exhibit 4 and incorporated herein by reference, pursuant to which, among other things, Mr. Tringali agreed to be named as a nominee in any proxy materials prepared by the Issuer or the Fund in relation to the Annual Meeting, to serve as a director of the Issuer if elected and, in such capacity, to act in the best interests of the shareholders of the Issuer and to exercise independent judgment in accordance with his fiduciary duties.

The Fund may also wish to exercise its right to inspect certain books and records of the Issuer pursuant to Article 116 of the Colorado Business Corporations Act in order to identify and communicate with other shareholders in connection with any solicitation of proxies in support of its nominees and to obtain additional information about the Issuer, and the Fund may demand that the Issuer make such books and records available.

2. Paragraphs (a), (b) and (c) of Item 5 of the Schedule 13D shall hereby be amended and restated in full as follows:

(a, b) The percentages of beneficial ownership reported in this Item 5, and on each Reporting Person’s cover page to this Schedule 13D, are based on a total of 12,424,026 shares of the Common Stock issued and outstanding as of November 7, 2022 as reported in the most recent quarterly report on Form 10-Q of the Issuer for its fiscal quarter ended September 30, 2022. All of the share numbers reported below, and on each Reporting Person’s cover page to this Schedule 13D, are as of March 10, 2023, unless otherwise indicated. The cover page to this Schedule 13D for each Reporting Person is incorporated by reference in its entirety into this Item 5(a, b).

The Fund directly holds, and thus has sole voting and dispositive power over, 905,008 shares of Common Stock, of which 1,000 shares are held of record. The GP, as sole general partner of the Fund, also has sole authority to vote (or direct the vote of), and to dispose (or direct the disposal) of, these shares of Common Stock on behalf of the Fund, and Mr. Lynch has shared authority to vote (or direct the vote of), and to dispose (or direct the disposal) of, these shares on behalf of the GP. Accordingly, each of the Reporting Persons beneficially owns 905,008 shares of Common Stock, or approximately 7.3% of the outstanding shares of Common Stock, and the Reporting Persons beneficially own, in the aggregate, 905,008 shares of Common Stock, or approximately 7.3% of the outstanding shares of Common Stock. None of Messrs. Jacobs, Petito and Yanagi has beneficial ownership of any shares of Common Stock.

(c) Except as otherwise described in this Schedule 13D, no Reporting Person, other than the Fund as set forth in the table below, effected any transaction in shares of Common Stock during the period from January 9, 2023 (the date 60 days prior to the filing of this Schedule 13D) to March 10, 2023:

The above listed transactions were effected pursuant to the assignment of Put Options sold by the Fund, as described in Item 6, which is incorporated by reference into this Item 5(c). Each of the Put Options underlying the above listed transactions was sold by the Fund on the same date as the assignment and corresponding purchase set forth above.

3. Item 7 of the Schedule 13D shall hereby be amended by adding the following Exhibits:

Exhibit 3     Letter from Mill Road Capital III, L.P. to Natural Gas Services Group, Inc. dated March 10, 2023.

Exhibit 4     Nomination Agreement between Mill Road Capital III, L.P. and Donald J. Tringali dated March 10, 2023.

4. Except as expressly modified hereby, all provisions of the Schedule 13D shall continue in full force and effect.

[signature page follows]

Signature

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Exhibit 99.3

Mill Road Capital III, L.P.

382 Greenwich Avenue, Suite One

Greenwich, CT 06830

(203) 987-3500

March 10, 2023

Via FEDEX and E-mail

Natural Gas Services Group, Inc.

404 Veterans Airpark Lane, Suite 300

Midland, TX 79705

Attn: Corporate Secretary

Ladies and Gentlemen:

Mill Road Capital III, L.P., a Cayman Islands exempted limited partnership (“Mill Road Capital”), pursuant to Section 1(b)(3)¹ of Article II of the Bylaws (the “Bylaws”) of Natural Gas Services Group, Inc., a Colorado corporation (the “Company”), hereby notifies the Company that it intends to nominate two (2) persons for election to the Board of Directors of the Company (the “Board”) at the 2023 Annual Meeting of Shareholders of the Company, or any other meeting of shareholders held in lieu thereof, and any adjournments, postponements, reschedulings or continuations thereof (the “Annual Meeting”).

This letter, including the Exhibits attached hereto, is referred to as the “Notice.” The persons Mill Road Capital intends to nominate for election to the Board are Mr. Justin C. Jacobs and Mr. Donald J. Tringali (each a “Nominee” and collectively, the “Nominees”). This Notice, in addition to being a notice of nomination under Section 1(b)(3) of Article II of the Bylaws, can also be deemed to be a request that the Company name the Nominees in its proxy statement as nominees for election to the Board at the Annual Meeting.

To the extent that the Company might purport to increase the size of the Board and/or the number of directors to be elected at the Annual Meeting, Mill Road Capital reserves the right to nominate additional nominees (each, an “Additional Nominee”) for election to the Board at the Annual Meeting. Any such additional nominations would be without prejudice to the issue of whether such attempted action by the Company was valid under the circumstances. Additionally, if, due to death, disability or other unforeseen circumstance, any Nominee or any Additional Nominee is unable to stand for election at the Annual Meeting, Mill Road Capital reserves the right to nominate one or more alternate nominees, as applicable, in place of such Nominee or Additional Nominee(s) (each an “Alternate Nominee”). In either event, Mill Road Capital will give prompt notice to the Company of its intent to nominate any Additional Nominees or Alternate Nominees at the Annual Meeting. Except where the context otherwise requires, the term “Nominee” as used in this Notice shall be deemed to include one or more Additional Nominees or Alternate Nominees, as applicable.

In accordance with Section 1(b)(3)(g) of Article II of the Bylaws, Mill Road Capital demands that the Corporate Secretary of the Company provide to Mill Road Capital, via e-mail to Justin C. Jacobs at jjacobs@millroadcapital.com with a copy to John D. Hancock at jhancock@foleyhoag.com, within one (1) business day after delivery of this Notice to the Company, a copy (in Word or other editable electronic format) of the Company’s questionnaire for director nominees (the “Nominee Questionnaire”). Mill Road Capital expects that the Nominee Questionnaire will be in the same form as any questionnaires utilized by the Company to gather information from individuals considered for nomination by the Board as a director of the Company.

Pursuant to Section 1(b)(3) of Article II of the Bylaws, the undersigned hereby sets forth the following:

MILL ROAD CAPITAL III LP

A PARTNERSHIP

ATTN THOMAS E. LYNCH

382 GREENWICH AVE-SUITE ONE

GREENWICH, CT 06830

Pursuant to Rule 14a-19(b) under the Securities Exchange Act of 1934, as amended (the “Exchange Act”), (a) this notice has been postmarked or transmitted electronically to the Company at its principal executive office no later than 60 calendar days prior to the anniversary of the date of the Company’s 2022 Annual Meeting of Shareholders (which was held on June 16, 2022), (b) this notice includes the names of all nominees for whom Mill Road Capital currently intends to solicit proxies and (c) Mill Road Capital hereby states that it intends to solicit the holders of shares representing at least 67% of the voting power of shares entitled to vote on the election of directors in support of director nominees other than the Company’s nominees. If any change occurs with respect to Mill Road Capital’s intent to solicit the holders of shares representing at least 67% of the voting power of shares entitled to vote on the election of directors in support of director nominees other than the Company’s nominees or with respect to the names of Mill Road Capital’s nominees, Mill Road Capital will notify the Company promptly.

In connection with any solicitation by Mill Road Capital of proxies in support of the Nominees, the Nominees may themselves solicit proxies. It is anticipated that certain regular employees or members of Mill Road Capital and affiliated entities will participate in any solicitation of proxies that Mill Road Capital may undertake in support of the Nominees. Such employees will receive no additional consideration if they assist in the solicitation of proxies. It is anticipated that any proxies would be solicited by mail, courier services, telephone, facsimile, press release, electronic mail, text message, website or social media posting, electronic forum, recorded communication, other form of electronic communication or in person. In connection with any solicitation of proxies in support of the Nominees, it is anticipated that Mill Road Capital will retain a proxy solicitor, who may assist with the solicitation of proxies. It is anticipated that the costs related to any solicitation of proxies, including expected expenditures for attorneys, accountants, public relations and financial advisors, proxy solicitors, advertising, printing, transportation and related expenses, will be borne by Mill Road Capital. To the extent legally permissible, Mill Road Capital may seek reimbursement from the Company for those expenses if one or more of the Nominees is elected. Mill Road Capital does not currently intend to submit the question of such reimbursement to a vote of the shareholders.

Except as set forth in this Notice, to the knowledge of Mill Road Capital as of the date hereof, (i) no Nominee has been convicted in a criminal proceeding (excluding traffic violations or similar misdemeanors) during the past ten years; (ii) no Nominee owns any securities of the Company (or any parent or subsidiary of the Company), directly or indirectly, beneficially or of record, or has purchased or sold any securities of the Company within the past two years, and no associate of any Nominee beneficially owns, directly or indirectly, any securities of the Company; (iii) no Nominee is, or was within the past year, a party to any contract, arrangements or understandings with any person with respect to any securities of the Company, including, but not limited to, joint ventures, loan or option arrangements, puts or calls, guarantees against loss or guarantees of profit, division of losses or profits, or the giving or withholding of proxies; (iv) there is no transaction or series of similar transactions since January 1, 2021, or currently proposed transaction or series of similar transactions, in which the Company or any of its subsidiaries was or is to be a participant, in which the amount involved exceeds $120,000 and in which any Nominee or any associate of any Nominee, or any member of the immediate family (including any person (other than a tenant or employee) sharing the same household) of any Nominee or of any associate of any Nominee, had or will have a direct or indirect material interest; (v) no Nominee or associate of any Nominee has any arrangement or understanding with any person (a) with respect to any future employment by the Company or its affiliates or (b) with respect to any future transactions to which the Company or any of its affiliates will or may be a party; (vi) no Nominee has any substantial interest, direct or indirect, by security holdings or otherwise, in any matter to be acted upon at the Annual Meeting⁴, except his interest in being

nominated for election as a director; (vii) there are no material proceedings to which any Nominee or any associate of any Nominee is a party adverse to the Company or any of its subsidiaries or has a material interest adverse to the Company or any of its subsidiaries; (viii) no occupation or employment (including positions or offices with the Company) is or was, during the last five years, carried on by any Nominee with the Company or any corporation or organization which is or was a parent, subsidiary or other affiliate of the Company; (ix) there exist no family relationships between any Nominee and any other Nominee, or any director or executive officer of the Company or any person known by Mill Road Capital or any Nominee to be nominated or chosen by the Company to become a director or executive officer of the Company⁵; (x) during the last ten years, no Nominee was involved in any of the events that are described in Item 401(f) of Regulation S-K and that are material to an evaluation of the ability or integrity of such Nominee to become a director of the Company; and (xi) no Nominee or associate of any Nominee has been awarded or paid, earned or received any cash compensation, cash bonuses, deferred compensation, compensation pursuant to plans, or other compensation from, or in respect of services rendered to or on behalf of, the Company and its subsidiaries that is required to be disclosed under, or is subject to any arrangement described in, Item 402 of Regulation S-K.

Mill Road Capital expects that, at the request of the Board, each Nominee will furnish to the Company such other information as the Board may need to determine the eligibility of such Nominee to serve as an independent director of the Company or that could be material to a reasonable shareholder’s understanding of the independence, or lack thereof, of such Nominee (without conceding the validity of any such requirement or request for additional information).

Mill Road Capital understands that certain information regarding the Annual Meeting (including, but not limited to, the record date, the number of voting shares outstanding and the date, time and place of the Annual Meeting) and the Company (including, but not limited to, various committees of the Board and deadlines for shareholder proposals, compensation of directors and beneficial ownership of the Company’s securities) will be set forth in the Company’s proxy statement on Schedule 14A, to be filed with the Commission by the Company with respect to the Annual Meeting, and in certain other Commission filings made or to be made by the Company and third parties under Sections 13 and 16 of the Exchange Act. To the extent the Company believes any such information is required to be set forth in this Notice, Mill Road Capital hereby refers the Company to such filings. Mill Road Capital accepts no responsibility for any information set forth in any such filings not provided by Mill Road Capital.

The Exhibits attached hereto are hereby incorporated into and made a part of this Notice. Accordingly, all matters disclosed in any part of this Notice, including the Exhibits, shall be deemed disclosed for all purposes of this Notice. Any capitalized term appearing in one of the Exhibits that is not defined in such Exhibit shall have the meaning given to such term in the body of this Notice or in such other Exhibit,that defines such term, as the case may be, as applicable.

Mill Road Capital trusts that this Notice complies in all respects with the Bylaws and applicable law. If the Company believes this Notice is incomplete or otherwise deficient in any respect, please notify us immediately in writing of such alleged deficiencies. Mill Road Capital reserves the right, following receipt of any such notice, to either challenge, or attempt to cure, any alleged deficiencies. Mill Road Capital also reserves the right to give further notice of additional business or nominations to be conducted or made at the Annual Meeting or other meeting of the Company’s shareholders, to revise the nominations described herein, or not to present any one or more nominations described herein.

Please be advised that, notwithstanding the compliance by Mill Road Capital with the relevant provisions of the Bylaws, neither the delivery of this Notice in accordance with the terms of the Bylaws nor the delivery of additional information, if any, provided to the Company from and after the date hereof by or on behalf of Mill Road Capital or any other person shall be deemed to constitute an admission that this Notice is in any way defective or as to the legality or enforceability of any particular provision of the Bylaws or any other matter, or a waiver by Mill Road Capital or any other person of its right to contest or challenge the enforceability thereof or of any other matter.

If this Notice shall be deemed for any reason by a court of competent jurisdiction to be ineffective with respect to the nomination of any of the Nominees at the Annual Meeting, or if any individual Nominee shall be unable to serve for any reason, then in addition to any other rights or remedies Mill Road Capital may have, this Notice shall continue to be effective with respect to the remaining Nominee(s) and as to any replacement Nominee(s) selected by Mill Road Capital.

Please address any correspondence or questions to Mill Road Capital Management LLC, 382 Greenwich Avenue, Suite One, Greenwich, CT 06830, Attention: Justin C. Jacobs, telephone (203) 987-3505, email: jjacobs@millroadcapital.com (with a copy to our counsel, Foley Hoag LLP, Seaport West, 155 Seaport Blvd., Boston, MA 02210, Attention: John D. Hancock, Esq., telephone (617) 832-1201, email: jhancock@foleyhoag.com).

[The remainder of this page is intentionally left blank.]

Donald J. Tringali

Exhibit A

Information regarding Mill Road Capital

Section 1(b)(3)(d) of Article II of the Bylaws

Information concerning any direct or indirect beneficial ownership of any equity or derivative interests in any principal competitor of the corporation held by such Proposing Shareholder, beneficial owner, Shareholder Associated Person and each nominee, and any direct or indirect interest of any of the preceding persons in any contract with the corporation, any affiliate of the corporation or any principal competitor of the corporation (including, in any such case, any employment agreement, collective bargaining agreement or consulting agreement).

Neither Mill Road Capital nor, to the information and belief of Mill Road Capital, any Shareholder Associated Persons (as that term is defined in the Bylaws) of Mill Road Capital (“MRC Shareholder Associated Persons”) directly or indirectly beneficially owns any equity or derivative interests in any entity that Mill Road Capital understands to be a principal competitor of the Company.¹

Neither Mill Road Capital nor, to the information and belief of Mill Road Capital, any MRC Shareholder Associated Persons has any direct or indirect interest in any contract with the Company, any affiliate of the Company² or any principal competitor of the Company.

Section 1(b)(3)(e) of Article II of the Bylaws

A list of all transactions by such Proposing Shareholder, beneficial owner and any Shareholder Associated Person involving any securities of the corporation, derivative interests, voting agreements or other control or economic interests in the corporation within the six-month period prior to the date of the notice.

The table below lists transactions in shares of Common Stock by Mill Road Capital during period beginning on June 18, 2020, the date of Mill Road Capital’s initial investment in the Company, and ending on the date of the Notice (the “Reporting Period”). Except for purchases in connection with the assignment of Put Options (as

defined below) (identified as “PUT” in the table), each of the below listed transactions was conducted in the ordinary course of business on the open market for cash, and the purchase and sale prices do not reflect brokerage commissions paid. All purchases of Common Stock were funded by working capital, which may, at any given time, include margin loans made by brokerage firms in the ordinary course of business.

The table below lists sales of standard American-style, exchange-traded put options (“Put Options“) by Mill Road Capital during the Reporting Period. Each of the below listed transactions was conducted in the ordinary course of business on the open market for cash, and the sale prices do not reflect brokerage commissions paid.

Each of the Put Options gives the option’s counterparty the right (but not the obligation) to sell to Mill Road Capital, on or before the option’s expiration date, the number of shares of Common Stock underlying the option, at a sale price per share equal to the option’s strike price per share. If a Put Option is assigned on or before its expiration date, Mill Road Capital must purchase the shares of Common Stock underlying the option in exchange for the option’s aggregate exercise price.

On information and belief, except as set forth above, there have been no transactions involving Mill Road Capital or any MRC Shareholder Associated Persons and any securities of the Company, derivative interests, voting agreements or other control or economic interests in the Company during the Reporting Period.

Section 1(b)(3)(h)(i) of Article II of the Bylaws

The name and address of the Proposing Shareholder as they appear on the corporation’s books and of the beneficial owner, if any, on whose behalf the nomination is being made.

The name and address of Mill Road Capital as we believe they appear on the Company’s books, are:

MILL ROAD CAPITAL III LP

A PARTNERSHIP

ATTN THOMAS E. LYNCH

382 GREENWICH AVE-SUITE ONE

GREENWICH, CT 06830

Mill Road Capital is not purporting to act on behalf of another beneficial owner of the shares of Common Stock owned beneficially or of record by Mill Road Capital.

Section 1(b)(3)(h)(ii) of Article II of the Bylaws

The class and number of shares of the corporation which are owned by the Proposing Shareholder (beneficially and of record) and owned by the beneficial owner, if any, on whose behalf the nomination is being made, as of the date of the Proposing Shareholder’s notice, and a representation that the Proposing Shareholder will notify the corporation in writing of the class and number of such shares owned of record and beneficially as of the record date for the meeting within five business days after the record date for such meeting.

Mill Road Capital is the beneficial owner of 905,008 shares of Common Stock, or approximately 7.3% of the Common Stock, 1,000 shares of which are held of record. Mill Road Capital’s address is 382 Greenwich Avenue, Suite One, Greenwich, Connecticut 06830. Mill Road Capital will notify the Company in writing of the class and number of shares owned of record by it within five business days after the record date for the Annual Meeting (or, if the Company seeks to prevent Mill Road Capital’s compliance with such reporting obligation by failing to publicly disclose, in a communication complying with Regulation FD, the record date for the Annual Meeting a reasonable time in advance thereof, within five business days after the date of the Company’s public announcement of such record date).

Section 1(b)(3)(h)(iii) of Article II of the Bylaws

A description of any agreement, arrangement, or understanding with respect to such nomination between or among the Proposing Shareholder or the beneficial owner, if any, on whose behalf the nomination is being made and any of their Shareholder Associated Persons (including their names) acting in concert with any of the foregoing, and a representation that the Proposing Shareholder will notify the corporation in writing of any such agreement, arrangement, or understanding in effect as of the record date for the meeting within five business days after the record date for such meeting.

Mill Road Capital has entered into a Nomination Agreement with Mr. Tringali pursuant to which, among other things, Mr. Tringali will be indemnified against certain potential liabilities that might arise in connection with being named as a Nominee and related matters. Mill Road Capital will also reimburse Mr. Tringali or directly pay for certain expenses, which Mill Road Capital expects to be nominal, that may be incurred by Mr. Tringali in connection with his serving as a Nominee. The agreement addresses certain additional matters, including, among other things, representations of Mr. Tringali as to certain matters such as the accuracy of information provided to Mill Road Capital, Mr. Tringali’s acknowledgement of his fiduciary obligations to the shareholders of NGS, if elected, and his obligation to update information provided to Mill Road Capital. Except for the agreement described above and as otherwise set forth in the Notice, there is no agreement, arrangement or understanding between or among Mill Road Capital, any MRC Shareholder Associated Person and any Nominee or other person or persons with respect to Mill Road Capital’s nomination of the Nominees. Mill Road Capital will notify the Company in writing of any such agreement, arrangement or understanding in effect as of the record date for the Annual Meeting within five business days after the record date (or, if the Company seeks to prevent Mill Road Capital’s compliance with such reporting obligation by failing to publicly disclose, in a communication complying with Regulation FD, the record date for the Annual Meeting a reasonable time in advance thereof, within five business days after the date of the Company’s public announcement of such record date).

Section 1(b)(3)(h)(iv) of Article II of the Bylaws

A description of any agreement, arrangement, or understanding (including any derivative or short positions, profit interests, options, hedging transactions, and borrowed or loaned shares) that has been entered into as of the date of the Proposing Shareholder’s notice by, or on behalf of, the Proposing Shareholder, the beneficial owner or any Shareholder Associated Person, if any, on whose behalf the nomination is being made, the effect or intent of which is to mitigate loss to, manage risk or benefit of share price changes for, or increase or decrease the voting power of such person or Shareholder Associated Person with respect to shares of stock of the corporation, and a representation that the Proposing Shareholder will notify the corporation in writing of any such agreement, arrangement, or understanding in effect as of the record date for the meeting within five business days after the record date for such meeting.

Mill Road Capital is a party to the Put Options that have not expired or been assigned.

Except as set forth above and elsewhere in the Notice, Mill Road Capital is not, and on information and belief, no MRC Shareholder Associated Person is, a party to any agreement, arrangement or understanding of the type described in Section 1(b)(3)(h)(iv) of Article II of the Bylaws. Mill Road Capital will notify the Company in writing of any such agreement, arrangement or understanding in effect as of the record date for the Annual Meeting within five business days after the record date for the Annual Meeting (or, if the Company seeks to prevent Mill Road Capital’s compliance with such reporting obligation by failing to publicly disclose, in a communication complying with Regulation FD, the record date for the Annual Meeting a reasonable time in advance thereof, within five business days after the date of the Company’s public announcement of such record date).

Section 1(b)(3)(h)(v) of Article II of the Bylaws

A representation that the Proposing Shareholder is a holder of record of shares of the corporation entitled to vote at the meeting and intends to appear in person or by proxy at the meeting to nominate the person or persons specified in the notice.

Mill Road Capital hereby represents that it is a shareholder of record of Common Stock entitled to vote at the Annual Meeting for the election of directors and that it intends to continue to be a holder of record through the Annual Meeting and to appear in person or by proxy at the Annual Meeting to nominate the Nominees specified herein.

Section 1(b)(3)(h)(v) of Article II of the Bylaws

A representation whether the Proposing Shareholder intends to deliver a proxy statement and/or form of proxy to holders of at least the percentage of the corporation’s outstanding capital stock required to approve the nomination and/or otherwise to solicit proxies from shareholders in support of the nomination.

Mill Road Capital’s current intention is to deliver a proxy statement and/or form of proxy to holders of at least the percentage of the Company’s outstanding capital stock required to approve the nomination and/or otherwise to solicit proxies from shareholders in support of the nomination of the Nominees.

Other Information

Set forth below is certain additional information regarding Mill Road Capital III, L.P., Mill Road Capital III GP LLC (“Fund III GP”) and Mill Road Capital Management LLC, which may, among other things, be deemed to be associates of Mr. Jacobs or members of a group. By including such information, Mill Road Capital does not concede that any such information is required to be disclosed in this Notice.

Mill Road Capital is a Cayman Islands exempted limited partnership. The principal business of Mill Road Capital is to operate as an investment firm that focuses primarily on investments in small, publicly traded companies.

The general partner of Mill Road Capital is Fund III GP, and the principal business of Fund III GP is to act as the sole general partner of Mill Road Capital. The address of Fund III GP is 382 Greenwich Avenue, Suite One, Greenwich, Connecticut 06830. The name, business address, present principal occupation and employment history of each person controlling Fund III GP are set forth at the end of this Exhibit A. Each of Thomas Lynch, Mr. Jacobs, Deven Petito and Eric Yanagi is a Management Committee Director of Fund III GP. Mr. Lynch has shared power to vote and dispose of the shares of Common Stock beneficially owned by Mill Road Capital. None of Messrs. Jacobs, Petito or Yanagi has beneficial ownership of any shares of Common Stock.

Mill Road Capital Management LLC is a Delaware limited liability company and an affiliate of Fund III GP (“Mill Road Mgtco”). The principal business of Mill Road Mgtco is to provide advisory and administrative services to Mill Road Capital and certain other investment funds and accounts. The address of Mill Road Mgtco is 382 Greenwich Avenue, Suite One, Greenwich, Connecticut 06830.

Set forth below are the name, present principal occupation or employment, and material occupations, positions, offices or employment for the past five years of each member of the Management Committee of Fund III GP, which controls Fund III GP. The principal business address of each member of the Management Committee of Fund III GP, other than Mr. Yanagi, is 382 Greenwich Avenue, Suite One, Greenwich, Connecticut 06830, and the principal business address of Mr. Yanagi is 400 Oyster Point Blvd., Suite 526, South San Francisco, CA 94080.

Thomas E. Lynch is a Management Committee Director of Fund III GP. Mr. Lynch’s present principal occupation or employment is as a Management Committee Director of Fund III GP and of Mill Road Mgtco, which provides advisory and administrative services to Fund III GP. Mr. Lynch is also the Senior Managing Director of Mill Road Mgtco. Prior to forming Mill Road Mgtco, Mr. Lynch was the founder and a Managing Director of Lazard Capital Partners. Prior to Lazard, Mr. Lynch was a Managing Director at The Blackstone Group and previously, was a consultant at Monitor Group Company LP, the consulting firm founded by Michael Porter.

Justin C. Jacobs is a Management Committee Director of Fund III GP. Mr. Jacobs’ present principal occupation or employment is as a Management Committee Director of Fund III GP and of Mill Road Mgtco, which provides advisory and administrative services to Fund III GP. Mr. Jacobs is also a Managing Director of Mill Road Mgtco. Prior to joining Mill Road Mgtco, Mr. Jacobs was employed at LiveWire Capital, an investment and management group backed primarily by The Blackstone Group and THL, formerly Thomas Lee Partners, that focused on operationally intensive buyouts of middle market companies. While employed at LiveWire, he held various operational positions in numerous portfolio companies, including interim Chief Operating Officer, in addition to investment responsibilities. Before joining LiveWire, Mr. Jacobs was an investment professional in the private equity division of The Blackstone Group.

Deven Petito is a Management Committee Director of Fund III GP. Mr. Petito is responsible for origination and execution of private equity transactions as well as portfolio company monitoring and management. He also leads new idea generation and investment due diligence for Mill Road Mgtco’s public equity portfolio. Mr. Petito began his investing career in the Private Equity Group at Kohlberg Kravis Roberts & Co. (KKR). Prior to joining KKR, Mr. Petito worked in the Investment Banking Division at Morgan Stanley.

Eric Yanagi is a Management Committee Director of Fund III GP. Prior to joining Mill Road Mgtco, Mr. Yanagi was an investment professional at Nautic Partners, a middle-market private equity firm focused on healthcare, industrials, and services. Earlier in his career, he was an investment banker in the Mergers & Acquisitions Group at Credit Suisse.

Exhibit B-1

Nominee Information for Donald J. Tringali

Section 1(b)(3)(a) of Article II of the Bylaws

The name, age, business address, and residence address of each nominee proposed in such notice.

Section 1(b)(3)(b) of Article II of the Bylaws

The principal occupation or employment of each such nominee along with information regarding each nominee’s business and finance qualifications that relate to the nominee’s ability to serve as a director of the corporation.

Mr. Tringali serves as the Chief Executive Officer of Augusta Advisory Group, a boutique financial and business consulting firm providing a full range of executive, operations and corporate advisory services to companies, a position he has held since founding the firm in 2001. Prior to founding Augusta Advisory Group, Mr. Tringali served as the Executive Vice President of Telemundo Group, Inc., a major media company serving the Hispanic population in the United States, from 1996 to 2001. Mr. Tringali has extensive experience serving on the boards of directors of public and private companies, including service as chairman, as well as on the audit, compensation, and nominating and governance committees of those companies. He currently serves on the boards of directors of Wavedancer, Inc., a Nasdaq-traded provider of zero trust software solutions, Swiss Water Decaffeinated Coffee, Inc., a green coffee decaffinator traded on the Toronto Stock Exchange, and POSaBIT Systems Corporation, a point-of-sale payments company focusing on the cannabis industry that is traded on the Canadian Stock Exchange. Mr. Tringali served as a director, and later as the Chairman of the Board, of National Technical Systems, Inc., a Nasdaq-traded international testing and engineering firm, from 1999 through its sale to a private equity firm in 2013. He is the former Executive Chairman of the Board of Cartesian, Inc., a Nasdaq-traded international telecommunications consulting company that was sold to a private equity group in 2018. Mr. Tringali began his career as a corporate attorney in Los Angeles, where he represented public and private companies in general business matters and mergers and acquisitions transactions. Mr. Tringali holds a Bachelor of Arts in Economics from UCLA and a Juris Doctor from Harvard Law School. Mill Road Capital believes that Mr. Tringali’s extensive board experience, including as a member or chairman of audit, compensation, and nominating and governance committees, combined with his experience as a public company executive, will enable him to contribute valuable insights into effective governance and oversight systems at the Company that will improve value for all shareholders.

Section 1(b)(3)(c) of Article II of the Bylaws

The class and number of shares of capital stock of the corporation which are owned of record and beneficially by each such nominee (if any).

Mill Road Capital understands that Mr. Tringali does not own, beneficially or of record, any shares of Common Stock or any other capital stock of the Company.

Section 1(b)(3)(d) of Article II of the Bylaws

Information concerning any direct or indirect beneficial ownership of any equity or derivative interests in any principal competitor of the corporation held by such Proposing Shareholder, beneficial owner, Shareholder Associated Person and each nominee, and any direct or indirect interest of any of the preceding persons in any contract with the corporation, any affiliate of the corporation or any principal competitor of the corporation (including, in any such case, any employment agreement, collective bargaining agreement or consulting agreement).

Mill Road Capital understands that Mr. Tringali does not directly or indirectly beneficially own any equity or derivative interests in any entity that either Mill Road Capital or Mr. Tringali understands to be a principal competitor of the Company.

Mill Road Capital understands that Mr. Tringali does not have any direct or indirect interest in any contract with the Company, any affiliate of the Company or any principal competitor of the Company.

Section 1(b)(3)(e) of Article II of the Bylaws

A list of all transactions by such Proposing Shareholder, beneficial owner and any Shareholder Associated Person involving any securities of the corporation, derivative interests, voting agreements or other control or economic interests in the corporation within the six-month period prior to the date of the notice.

None.

Section 1(b)(3)(f) of Article II of the Bylaws:

Such other information concerning each such nominee as would be required to be disclosed in a proxy statement soliciting proxies for the election of such nominee as a director in an election contest (even if an election contest is not involved) or that is otherwise required to be disclosed, under Section 14(a) of the Exchange Act.

Mill Road Capital does not believe that any information concerning Mr. Tringali would be required to be disclosed in a proxy statement soliciting proxies for the election of Mr. Tringali as a director of the Company in an election contest, other than information otherwise disclosed in the Notice.

Exhibit B-2

Tringali Undertaking

[See attached]

Exhibit C-1

Nominee Information for Justin C. Jacobs

Section 1(b)(3)(a) of Article II of the Bylaws

The name, age, business address, and residence address of each nominee proposed in such notice.

Section 1(b)(3)(b) of Article II of the Bylaws:

The principal occupation or employment of each such nominee along with information regarding each nominee’s business and finance qualifications that relate to the nominee’s ability to serve as a director of the corporation.

Mr. Jacobs is a Management Committee Director of Mill Road Capital Management LLC, where he has worked since 2005. Mill Road Capital Management is an investment firm focused on investments in small, publicly traded companies. The firm manages multiple funds with approximately $1.0 billion of assets under management. From 1999 to 2004, Mr. Jacobs was employed at LiveWire Capital, an investment and management group backed primarily by The Blackstone Group and Thomas Lee Partners that focused on operationally intensive buyouts of middle market companies. While employed at LiveWire, he held various operational positions in numerous portfolio companies, including interim Chief Operating Officer, in addition to investment responsibilities. Before joining LiveWire, Mr. Jacobs was an investment professional in the private equity division of The Blackstone Group from 1996 to 1999. Mr. Jacobs holds a B.S. from the McIntire School of Commerce at the University of Virginia and is currently a member of the Board of Directors of Swiss Water Decaffeinated Coffee, Inc. He previously served as a member of the Boards of Directors of several public companies, Ecology and Environment, Inc., Galaxy Nutritional Foods, Inc., National Technical Systems, Inc., and School Specialty, Inc., and numerous private companies, including Lignetics, Inc., Mother’s Market & Kitchen, Inc., PRT Growing Services LTD and Rubios Restaurants, Inc. Through his work, Mr. Jacobs has developed expertise in capital markets transactions, mergers and acquisitions, capital allocation and strategic reviews, as well as significant experience with executive compensation, shareholder communications and the development of both short- and long-term strategic growth plans. His experience includes challenging turnaround situations. Mill Road Capital believes that Mr. Jacobs’ significant experience in both operational and oversight roles, particularly with small, publicly traded companies, positions him well to help the Company navigate its current management transitions and to establish disciplined governance practices that will focus the Company’s management on shareholder value creation.

Section 1(b)(3)(c) of Article II of the Bylaws

The class and number of shares of capital stock of the corporation which are owned of record and beneficially by each such nominee (if any).

Mr. Jacobs is a Management Committee Director of Mill Road Capital III GP LLC, the sole general partner of Mill Road Capital III, L.P., which has the sole power to vote and dispose of the 905,008 shares of Common Stock beneficially owned by Mill Road Capital III, L.P., of which 1,000 shares are held of record by Mill Road Capital III, L.P.

Mr. Jacobs does not own, beneficially or of record, any shares of the capital stock of the Company.

Section 1(b)(3)(d) of Article II of the Bylaws

Information concerning any direct or indirect beneficial ownership of any equity or derivative interests in any principal competitor of the corporation held by such Proposing Shareholder, beneficial owner, Shareholder Associated Person and each nominee, and any direct or indirect interest of any of the preceding persons in any contract with the corporation, any affiliate of the corporation or any principal competitor of the corporation (including, in any such case, any employment agreement, collective bargaining agreement or consulting agreement).

Mr. Jacobs does not directly or indirectly beneficially own any equity or derivative interests in any entity that either Mill Road Capital or Mr. Jacobs understands to be a principal competitor of the Company.

Mr. Jacobs does not have any direct or indirect interest in any contract with the Company, any affiliate of the Company or any principal competitor of the Company.

Section 1(b)(3)(e) of Article II of the Bylaws

A list of all transactions by such Proposing Shareholder, beneficial owner and any Shareholder Associated Person involving any securities of the corporation, derivative interests, voting agreements or other control or economic interests in the corporation within the six-month period prior to the date of the notice.

Mr. Jacobs is a Management Committee Director of Mill Road Capital III GP LLC, the sole general partner of Mill Road Capital III, L.P. See Exhibit A for information regarding transactions by Mill Road Capital and MRC Shareholder Associated Persons during the Reporting Period involving any securities of the Company, derivative interests, voting agreements or other control or economic interests in the Company.

Mr. Jacobs has not engaged in any such transactions.

Section 1(b)(3)(f) of Article II of the Bylaws

Such other information concerning each such nominee as would be required to be disclosed in a proxy statement soliciting proxies for the election of such nominee as a director in an election contest (even if an election contest is not involved) or that is otherwise required to be disclosed, under Section 14(a) of the Exchange Act.

Mill Road Capital does not believe that any information concerning Mr. Jacobs would be required to be disclosed in a proxy statement soliciting proxies for the election of Mr. Jacobs as a director of the Company in an election contest, other than information otherwise disclosed in the Notice.

Exhibit C-2

Jacobs Undertaking

[See attached]

Exhibit 99.4

Mill Road Capital III, L.P.

328 Greenwich Avenue, Suite One

Greenwich, Connecticut 06830

NOMINATION AGREEMENT

March 10, 2023

Donald J. Tringali

[***]

Dear Mr. Tringali:

This letter agreement relates to your agreement to become a nominee of Mill Road Capital III, L.P. (“Mill Road”) for election as an independent director (“Nominee”) of Natural Gas Services Group, Inc., a Colorado corporation (“NGS”). Mill Road desires to nominate you for election to the Board of Directors of NGS and potentially solicit proxies for your election to the Board of Directors of NGS (the “Board Process”).

A. Responsibilities of Nominee.

(1) You agree (i) to be named as a Nominee in any and all proxy materials prepared by Mill Road or, to the extent required by applicable law, NGS, (ii) to provide true and complete information concerning your background, experience, abilities and integrity as may be requested from time to time by Mill Road (including, without limitation, all information required by the Securities and Exchange Commission (the “SEC”) to be disclosed to the SEC or in a proxy statement prepared by Mill Road in connection with the Board Process or by the articles of incorporation or bylaws of NGS) and not to omit any information that may be material to an understanding of your background, experience, abilities and integrity, (iii) that your agreement to be a Nominee, and the information referred to in the foregoing clause (ii), may be publicly disclosed by Mill Road, in its proxy materials or otherwise, and (iv) if elected, to serve as a director of NGS, and in that capacity to act in the best interests of the NGS shareholders and to exercise your independent judgment in accordance with your fiduciary duties in all matters that come before the NGS Board of Directors. You represent that the information supplied to Mill Road in your completed questionnaire, in follow-up questions from Mill Road and any related supplement provided by you (together, the “Questionnaire”) relating to your being a Nominee is true and complete and does not omit any information that may be material to an understanding of your background, experience, abilities and integrity. In addition, you agree that, concurrently with your execution of this letter agreement, you will execute a consent in the form attached hereto as Exhibit A informing NGS that (i) you consent to being a Nominee, (ii) if elected, you consent to serving as a director of NGS, (iii) if elected, you intend to serve as a director for the full term for which you are standing election and (iv) makes certain representations required by the bylaws of NGS. You agree that you will promptly provide Mill Road with (i) any updates to the information you have previously supplied to Mill Road in order to satisfy your obligation under clause (ii) of the first sentence of this Section A(1) and your representations in the Questionnaire and (ii) such additional information as NGS may reasonably require in connection with your nomination for election to the NGS Board of Directors.

(2) The parties acknowledge and agree that you are not an employee or an agent or otherwise a representative of Mill Road, and that you are independent of, and not controlled by or acting at the direction of, Mill Road and that, if elected, you will be acting as a director, on behalf of all of the shareholders of NGS and will in no way be controlled by or acting at the direction of Mill Road. You shall have no authority to act as an agent of Mill Road and you shall not represent the contrary to any person.

(3) You further agree that (i) you will treat confidentially and not disclose to any third parties (unless compelled by law) any information relating to the Board Process that is non-public, confidential or proprietary in nature, including any such information received from or learned in discussions with Mill Road regarding the Board Process; (ii) you will not issue, publish or otherwise make any public statement or any other form of public communication relating to NGS, Mill Road or the Board Process without the prior written approval of Mill Road; and (iii) you will not agree to serve or be nominated to stand for election to the Board of Directors of NGS by (a) NGS, (b) any other stockholder of NGS (other than Mill Road and its affiliates) or (c) any other party, in each case without the prior written approval of Mill Road. Notwithstanding the foregoing, the obligations set forth clause (ii) above shall terminate and be of no further force or effect if you are elected to the Board of Directors of NGS.

B. Responsibilities of Mill Road. Notwithstanding anything in this letter agreement, Mill Road is not obligated to nominate you to the NGS Board of Directors or to commence or complete the Board Process.

C. Expenses; Termination. Mill Road agrees that, for the period from the date of this letter agreement until the earlier of (x) the 2023 annual meeting of shareholders of NGS or special meeting in lieu thereof, including any postponements, adjournments or rescheduling thereof (or, if the election or qualification of candidates to the NGS Board of Directors is contested on any grounds, such later date that such contest is resolved) and (y) the date you have been notified by Mill Road that it has abandoned the Board Process, Mill Road will (i) promptly reimburse you for all reasonable pre-approved expenses incurred in the performance of your responsibilities as a Nominee and (ii) directly pay for the reasonable legal fees and expenses incurred by one independent legal counsel selected collectively by, and acting on behalf of, all nominees proposed by Mill Road as independent directors of NGS (the “Independent Counsel”). This letter agreement and the obligations of the parties hereto shall terminate upon the earlier of the dates set forth in clauses (x) and (y) of the first sentence of this Section C (or upon the earlier mutual written consent of the parties hereto).

D. Indemnification.

(1) As a material inducement to you to become a Nominee, Mill Road hereby agrees to indemnify, defend and hold harmless you from and against any and all losses, claims, damages, liabilities, judgments, costs, and expenses (including reasonable fees and disbursements of counsel and costs of investigation) (collectively, “Losses”) to which you may become subject or which you may incur in connection with being made, or threatened with being

2

made, a party or witness (or in any other capacity) in any proceeding at law or in equity or before any governmental agency or board (whether civil, criminal, trial, appeal, administrative, formal, informal or investigative), arising out of or based upon your being a Nominee, except to the extent such Loss arises or results from your gross negligence, willful misconduct or any untrue statement or omission made by you or made by Mill Road in reliance upon and in conformity with information furnished by you in writing expressly for use in any document made available to the public; it being understood that you are furnishing the Questionnaire expressly for use in potential Mill Road proxy materials and other filings to be made publicly available.

(2) In the event of the commencement or threatened commencement of any action in respect of which you may seek indemnification from Mill Road hereunder, you will give prompt written notice thereof to Mill Road, the failure of which shall not relieve Mill Road of its indemnification obligations hereunder except to the extent that Mill Road is materially prejudiced as a result thereof. Mill Road shall timely pay all fees and disbursements of the Independent Counsel in respect of such action; however, you shall have the right to retain separate counsel, provided, that you shall be responsible for the fees of such counsel and costs of such participation unless either (i) you and Mill Road mutually agree to the retention of such counsel, or (ii) representation of you and other Nominees by the same counsel would be inappropriate due to actual or potential differing interests between you and them. Mill Road shall in no event be liable for any settlement by you of any such action affected without the prior written consent of Mill Road, which shall not be unreasonably withheld.

(3) Mill Road shall not settle, without your prior written consent (which you may withhold in your sole discretion), any action in any manner that would impose any penalty, obligation or limitation on you (other than monetary damages for which Mill Road agrees to be wholly responsible) or that would contain any language that could be viewed as an acknowledgement of wrongdoing on your part or otherwise as detrimental to your reputation.

(4) Your rights to indemnification under this letter agreement shall include the right to be advanced any and all expenses incurred in connection with any indemnifiable claim as such expenses are incurred.

(5) Notwithstanding anything to the contrary, if Mill Road has made payments to you pursuant to the indemnification and expense reimbursement provisions hereof and you subsequently are reimbursed by a third party therefor, you will promptly remit such subsequent reimbursement to Mill Road.

E. NGS Capital Stock. You acknowledge and agree that: (i) you do not beneficially own, directly or indirectly, any shares of capital stock of NGS, including without limitation any shares of Common Stock, par value $0.01 per share, of NGS (any shares of capital stock of NGS being “NGS Shares”), (ii) there exists no written or oral contract, agreement, arrangement, understanding, undertaking or other commitment (“Contract”) to which you are a party or are bound pursuant to which you (u) have the right to purchase or otherwise acquire from, or sell, tender, assign or otherwise transfer to, Mill Road (whether such right is exercisable immediately or only after the passage of time), any NGS Shares or any interest therein, (v) have granted Mill Road the right to purchase or otherwise acquire from, or sell, tender, assign or otherwise transfer to, you (whether such right is exercisable immediately or only after the passage of time), any

3

NGS Shares or any interest therein, (w) have the right to vote any NGS Shares owned of record or beneficially owned by Mill Road, (x) have granted Mill Road the right to vote any NGS Shares owned of record or beneficially owned by you, (y) have granted to Mill Road any proxy or power of attorney with respect to, or entered into a voting agreement or other arrangement with Mill Road with respect to the voting of, any NGS Shares owned of record or beneficially owned by you or (z) have been granted any proxy or power of attorney by Mill Road with respect to, or entered into a voting agreement or other arrangement with Mill Road with respect to the voting of, any NGS Shares owned of record or beneficially owned by Mill Road; (iii) there exists no Contract to which you are a party or are bound for the purpose of acquiring, holding, voting or disposing of any NGS Shares beneficially owned, directly or indirectly, by any affiliate or associate of Mill Road; (iv) until the conclusion of NGS’s 2023 Annual Meeting of Shareholders, including any adjournment or postponement thereof, you will promptly advise Mill Road orally and in writing in the event that you purchase or otherwise acquire any NGS Shares or any interest therein, or enter into any Contract to do any of the same; and (v) nothing in this letter agreement changes any of the items set forth in the foregoing clauses (i) through (iv) of this Section E, and this letter agreement does not create a Contract nor impose any limitation of any kind with respect to you or Mill Road acquiring, holding, voting or disposing of any NGS Shares.

F. General. Notices and other communications under this letter agreement shall be in writing and delivered by a nationally recognized overnight courier with tracking capability, if mailed to you, then to the address set forth above under your name, and, if mailed to Mill Road, then to the address indicated above in the letterhead. The failure of a party to insist upon strict adherence to any term contained herein shall not be deemed to be a waiver of such party’s rights thereafter to insist upon strict adherence to that term or to any other term contained herein. In the event that any one or more provisions of this letter agreement are deemed to be invalid, illegal or unenforceable by a court of competent jurisdiction, then such provision(s) shall be deemed severed to the least extent possible without affecting the validity, legality and enforceability of the remainder of this letter agreement. This letter agreement (i) shall be governed by and construed in accordance with the laws of the State of New York, without regard to its conflict of laws principles; (ii) contains the entire understanding of the parties with respect to the subject matter contained herein and may not be modified or amended expect by mutual written consent; (iii) shall inure to the benefit of and be binding upon the parties and their respective heirs, representatives, successors, and assigns; and (iv) may be executed in counterparts and delivered by facsimile or other electronic signatures.

[The remainder of this page is intentionally blank.]

4

EXHIBIT A

Form of Consent

[See attached]