<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with Wdesk from Workiva, formerly WebFilings-->
<!-- -->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://naturalgaservices.com/20141231" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:ngs="http://naturalgaservices.com/20141231" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <xsd:import namespace="http://fasb.org/us-gaap/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-gaap-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-roles-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-types-2014-01-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/arcrole/fact-explanatoryFact" schemaLocation="http://www.xbrl.org/lrr/arcrole/factExplanatory-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd" />
  <xsd:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/country/2013-01-31" schemaLocation="http://xbrl.sec.gov/country/2013/country-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2014-01-31" schemaLocation="http://xbrl.sec.gov/currency/2014/currency-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2014-01-31" schemaLocation="http://xbrl.sec.gov/dei/2014/dei-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2014-01-31" schemaLocation="http://xbrl.sec.gov/exch/2014/exch-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2013-01-31" schemaLocation="http://xbrl.sec.gov/invest/2013/invest-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/naics/2011-01-31" schemaLocation="http://xbrl.sec.gov/naics/2011/naics-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/sic/2011-01-31" schemaLocation="http://xbrl.sec.gov/sic/2011/sic-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/stpr/2011-01-31" schemaLocation="http://xbrl.sec.gov/stpr/2011/stpr-2011-01-31.xsd" />
  <xsd:annotation>
    <xsd:appinfo>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20141231_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20141231_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20141231_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20141231_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="BalanceSheets" roleURI="http://naturalgaservices.com/role/BalanceSheets">
        <link:definition>1001000 - Statement - Balance Sheets</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BalanceSheetsParenthetical" roleURI="http://naturalgaservices.com/role/BalanceSheetsParenthetical">
        <link:definition>1001501 - Statement - Balance Sheets (Parenthetical)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingencies" roleURI="http://naturalgaservices.com/role/CommitmentsAndContingencies">
        <link:definition>2124100 - Disclosure - Commitments and Contingencies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesFutureLeasePaymentsDetails" roleURI="http://naturalgaservices.com/role/CommitmentsAndContingenciesFutureLeasePaymentsDetails">
        <link:definition>2424403 - Disclosure - Commitments and Contingencies (Future Lease Payments) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesNarrativeDetails" roleURI="http://naturalgaservices.com/role/CommitmentsAndContingenciesNarrativeDetails">
        <link:definition>2424402 - Disclosure - Commitments and Contingencies (Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesTables" roleURI="http://naturalgaservices.com/role/CommitmentsAndContingenciesTables">
        <link:definition>2324301 - Disclosure - Commitments and Contingencies (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CreditFacility" roleURI="http://naturalgaservices.com/role/CreditFacility">
        <link:definition>2113100 - Disclosure - Credit Facility</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CreditFacilityDetails" roleURI="http://naturalgaservices.com/role/CreditFacilityDetails">
        <link:definition>2413401 - Disclosure - Credit Facility (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="DocumentAndEntityInformation" roleURI="http://naturalgaservices.com/role/DocumentAndEntityInformation">
        <link:definition>0001000 - Document - Document and Entity Information</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxes" roleURI="http://naturalgaservices.com/role/IncomeTaxes">
        <link:definition>2119100 - Disclosure - Income Taxes</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesComponentsOfDeferredTaxAssetsAndLiabilitiesDetails" roleURI="http://naturalgaservices.com/role/IncomeTaxesComponentsOfDeferredTaxAssetsAndLiabilitiesDetails">
        <link:definition>2419403 - Disclosure - Income Taxes (Components of Deferred Tax Assets and Liabilities) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesComponentsOfProvisionForIncomeTaxesDetails" roleURI="http://naturalgaservices.com/role/IncomeTaxesComponentsOfProvisionForIncomeTaxesDetails">
        <link:definition>2419402 - Disclosure - Income Taxes (Components of Provision for Income Taxes) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesIncomeTaxReconciliationDetails" roleURI="http://naturalgaservices.com/role/IncomeTaxesIncomeTaxReconciliationDetails">
        <link:definition>2419404 - Disclosure - Income Taxes (Income Tax Reconciliation) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesIncomeTaxesTables" roleURI="http://naturalgaservices.com/role/IncomeTaxesIncomeTaxesTables">
        <link:definition>2319301 - Disclosure - Income Taxes Income Taxes (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesNarrativeDetails" roleURI="http://naturalgaservices.com/role/IncomeTaxesNarrativeDetails">
        <link:definition>2419405 - Disclosure - Income Taxes (Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="OtherLongTermLiabilities" roleURI="http://naturalgaservices.com/role/OtherLongTermLiabilities">
        <link:definition>2116100 - Disclosure - Other Long-term Liabilities</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="OtherLongTermLiabilitiesDetails" roleURI="http://naturalgaservices.com/role/OtherLongTermLiabilitiesDetails">
        <link:definition>2416401 - Disclosure - Other Long-term Liabilities (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipment" roleURI="http://naturalgaservices.com/role/PropertyAndEquipment">
        <link:definition>2110100 - Disclosure - Property and Equipment</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipmentDetails" roleURI="http://naturalgaservices.com/role/PropertyAndEquipmentDetails">
        <link:definition>2410402 - Disclosure - Property and Equipment (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipmentTables" roleURI="http://naturalgaservices.com/role/PropertyAndEquipmentTables">
        <link:definition>2310301 - Disclosure - Property and Equipment (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnaudited" roleURI="http://naturalgaservices.com/role/QuarterlyFinancialDataUnaudited">
        <link:definition>2126100 - Disclosure - Quarterly Financial Data &#8211; Unaudited</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnauditedDetails" roleURI="http://naturalgaservices.com/role/QuarterlyFinancialDataUnauditedDetails">
        <link:definition>2426402 - Disclosure - Quarterly Financial Data - Unaudited (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnauditedTables" roleURI="http://naturalgaservices.com/role/QuarterlyFinancialDataUnauditedTables">
        <link:definition>2326301 - Disclosure - Quarterly Financial Data - Unaudited (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RentalActivity" roleURI="http://naturalgaservices.com/role/RentalActivity">
        <link:definition>2107100 - Disclosure - Rental Activity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RentalActivityDetails" roleURI="http://naturalgaservices.com/role/RentalActivityDetails">
        <link:definition>2407402 - Disclosure - Rental Activity (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RentalActivityTables" roleURI="http://naturalgaservices.com/role/RentalActivityTables">
        <link:definition>2307301 - Disclosure - Rental Activity (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StatementsOfCashFlows" roleURI="http://naturalgaservices.com/role/StatementsOfCashFlows">
        <link:definition>1004000 - Statement - Statements of Cash Flows</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StatementsOfIncome" roleURI="http://naturalgaservices.com/role/StatementsOfIncome">
        <link:definition>1002000 - Statement - Statements of Income</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StatementsOfStockholdersEquity" roleURI="http://naturalgaservices.com/role/StatementsOfStockholdersEquity">
        <link:definition>1003000 - Statement - Statements of Stockholders' Equity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensation" roleURI="http://naturalgaservices.com/role/StockBasedCompensation">
        <link:definition>2123100 - Disclosure - Stock-Based Compensation</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationRestrictedStockActivityDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationRestrictedStockActivityDetails">
        <link:definition>2423403 - Disclosure - Stock-Based Compensation (Restricted Stock Activity) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationRestrictedStockNarrativeDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationRestrictedStockNarrativeDetails">
        <link:definition>2423402 - Disclosure - Stock-Based Compensation (Restricted Stock Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationStockOptionActivityDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationStockOptionActivityDetails">
        <link:definition>2423406 - Disclosure - Stock-Based Compensation (Stock Option Activity) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationStockOptionsByExercisePriceRangeDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationStockOptionsByExercisePriceRangeDetails">
        <link:definition>2423407 - Disclosure - Stock-Based Compensation (Stock Options by Exercise Price Range) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationStockOptionsNarrativeDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationStockOptionsNarrativeDetails">
        <link:definition>2423404 - Disclosure - Stock-Based Compensation (Stock Options Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationSummaryOfUnvestedStockOptionsDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationSummaryOfUnvestedStockOptionsDetails">
        <link:definition>2423408 - Disclosure - Stock-Based Compensation (Summary of Unvested Stock Options) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationTables" roleURI="http://naturalgaservices.com/role/StockBasedCompensationTables">
        <link:definition>2323301 - Disclosure - Stock-Based Compensation (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationValuationAssumptionsDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationValuationAssumptionsDetails">
        <link:definition>2423405 - Disclosure - Stock-Based Compensation (Valuation Assumptions) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockholdersEquity" roleURI="http://naturalgaservices.com/role/StockholdersEquity">
        <link:definition>2122100 - Disclosure - Stockholders' Equity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockholdersEquityDetails" roleURI="http://naturalgaservices.com/role/StockholdersEquityDetails">
        <link:definition>2422401 - Disclosure - Stockholders' Equity (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPolicies" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPolicies">
        <link:definition>2101100 - Disclosure - Summary of Significant Accounting Policies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesConcentrationRiskDetails" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesConcentrationRiskDetails">
        <link:definition>2401404 - Disclosure - Summary of Significant Accounting Policies (Concentration Risk) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesIntangiblesDetails" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesIntangiblesDetails">
        <link:definition>2401406 - Disclosure - Summary of Significant Accounting Policies (Intangibles) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesNarrativeDetails" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesNarrativeDetails">
        <link:definition>2401403 - Disclosure - Summary of Significant Accounting Policies (Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesPolicies" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesPolicies">
        <link:definition>2201201 - Disclosure - Summary of Significant Accounting Policies (Policies)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesPropertyAndEquipmentDetails" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesPropertyAndEquipmentDetails">
        <link:definition>2401405 - Disclosure - Summary of Significant Accounting Policies (Property and Equipment) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SummaryOfSignificantAccountingPoliciesTables" roleURI="http://naturalgaservices.com/role/SummaryOfSignificantAccountingPoliciesTables">
        <link:definition>2301302 - Disclosure - Summary of Significant Accounting Policies (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xsd:appinfo>
  </xsd:annotation>
  <xsd:element abstract="true" id="ngs_A1998StockOptionPlanMember" name="A1998StockOptionPlanMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_AccumulatedDepreciationRentalEquipment" name="AccumulatedDepreciationRentalEquipment" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ngs_CashEquivalentsQualificationMaximumOriginalMaturityOfShortTermInvestments" name="CashEquivalentsQualificationMaximumOriginalMaturityOfShortTermInvestments" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_CbFloatingRateMember" name="CbFloatingRateMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_CustomerDepositsDepositRequirementsLargeCustomContractsMaximumPercentage" name="CustomerDepositsDepositRequirementsLargeCustomContractsMaximumPercentage" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_DeferredAndOtherIncomeTaxExpenseBenefit" name="DeferredAndOtherIncomeTaxExpenseBenefit" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ngs_DefinedContributionPlanEligibilityAgeMinimum" name="DefinedContributionPlanEligibilityAgeMinimum" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_DefinedContributionPlanEmployerContributionAmount" name="DefinedContributionPlanEmployerContributionAmount" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ngs_DefinedContributionPlanEmployerContributionUltimateVestingPercentage" name="DefinedContributionPlanEmployerContributionUltimateVestingPercentage" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_DefinedContributionPlanEmployersMatchingContributionVestingTerm" name="DefinedContributionPlanEmployersMatchingContributionVestingTerm" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_DefinedContributionPlanRequisiteServicePeriod" name="DefinedContributionPlanRequisiteServicePeriod" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_DevonEnergyProductionIncMember" name="DevonEnergyProductionIncMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_DocumentAndEntityInformationAbstract" name="DocumentAndEntityInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_EmployeeServiceShareBasedCompensationNonvestedAwardsOutstandingNumberStockOptions" name="EmployeeServiceShareBasedCompensationNonvestedAwardsOutstandingNumberStockOptions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ngs_EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsOutstandingRollForward" name="EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsOutstandingRollForward" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsWeightedAverageGrantDateFairValueRollForward" name="EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsWeightedAverageGrantDateFairValueRollForward" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_EmployeeServiceShareBasedCompensationVestedInPeriodStockOptions" name="EmployeeServiceShareBasedCompensationVestedInPeriodStockOptions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_EmployeeServiceSharebasedCompensationNonvestedAwardsOutstandingStockOptionsWeightedAverageGrantDateFairValue" name="EmployeeServiceSharebasedCompensationNonvestedAwardsOutstandingStockOptionsWeightedAverageGrantDateFairValue" nillable="true" substitutionGroup="xbrli:item" type="num:perShareItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_EmployeeServiceSharebasedCompensationNonvestedAwardsVestedinPeriodStockOptionsWeightedAverageGrantDateFairValue" name="EmployeeServiceSharebasedCompensationNonvestedAwardsVestedinPeriodStockOptionsWeightedAverageGrantDateFairValue" nillable="true" substitutionGroup="xbrli:item" type="num:perShareItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_EogResourcesIncMember" name="EogResourcesIncMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_GainLossOnSettlementOfDeferredRevenueLiability" name="GainLossOnSettlementOfDeferredRevenueLiability" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ngs_IntangibleAssetsAccumulatedAmortization" name="IntangibleAssetsAccumulatedAmortization" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ngs_IntangibleAssetsLineItems" name="IntangibleAssetsLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_IntangibleAssetsTable" name="IntangibleAssetsTable" nillable="true" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_InventoryValuationReservesDeductions" name="InventoryValuationReservesDeductions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_LandAndBuildingExcludingLeaseholdImprovementsMember" name="LandAndBuildingExcludingLeaseholdImprovementsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_LiborBasedRateMember" name="LiborBasedRateMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityAllowableShareOfTotalCommitmentAmountAttributableToGeneralInventoryComponent" name="LineOfCreditFacilityCurrentBorrowingCapacityAllowableShareOfTotalCommitmentAmountAttributableToGeneralInventoryComponent" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleAccountsReceivable" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleAccountsReceivable" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleEquipmentInventory" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleEquipmentInventory" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleGeneralInventory" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleGeneralInventory" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityDefaultTriggerCertainDefaultsOfOtherCompanyIndebtednessAmount" name="LineOfCreditFacilityDefaultTriggerCertainDefaultsOfOtherCompanyIndebtednessAmount" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityDefaultTriggerRenderingOfCertainJudgmentsAmount" name="LineOfCreditFacilityDefaultTriggerRenderingOfCertainJudgmentsAmount" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityPotentialIncreaseInBorrowingCapacity" name="LineOfCreditFacilityPotentialIncreaseInBorrowingCapacity" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ngs_LineOfCreditFacilityPotentialMaximumBorrowingCapacity" name="LineOfCreditFacilityPotentialMaximumBorrowingCapacity" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineOfCreditFacilityReferenceRateNumberOfAllowableBorrowingsOutstanding" name="LineOfCreditFacilityReferenceRateNumberOfAllowableBorrowingsOutstanding" nillable="true" substitutionGroup="xbrli:item" type="xbrli:integerItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_LineofCreditFacilityCommitmentCoverageRatio" name="LineofCreditFacilityCommitmentCoverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_LineofCreditFacilityLeverageRatio" name="LineofCreditFacilityLeverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:pureItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_LongTermPurchaseCommitmentCashReceivedAsDiscountTowardFuturePurchases" name="LongTermPurchaseCommitmentCashReceivedAsDiscountTowardFuturePurchases" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ngs_LongTermPurchaseCommitmentLiabilityRelatedToDeferredDiscount" name="LongTermPurchaseCommitmentLiabilityRelatedToDeferredDiscount" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ngs_NonExecutiveEmployeesMember" name="NonExecutiveEmployeesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_OfficeEquipmentAndFurnitureMember" name="OfficeEquipmentAndFurnitureMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_OperatingLeasesFutureMinimumPaymentsDueAfterFourYears" name="OperatingLeasesFutureMinimumPaymentsDueAfterFourYears" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ngs_OperatingLeasesFutureMinimumPaymentsReceivableAfterTwoYears" name="OperatingLeasesFutureMinimumPaymentsReceivableAfterTwoYears" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ngs_OperatingLeasesOfLesseeMaximumTerm" name="OperatingLeasesOfLesseeMaximumTerm" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_OperatingLeasesOfLessorOriginalTerm" name="OperatingLeasesOfLessorOriginalTerm" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_OtherLiabilitiesLineItems" name="OtherLiabilitiesLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_OxyMember" name="OxyMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_PaymentsToSettleDeferredRevenueLiability" name="PaymentsToSettleDeferredRevenueLiability" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ngs_ProceedsFromPurchaseCommitmentDiscountNet" name="ProceedsFromPurchaseCommitmentDiscountNet" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_PromatconMember" name="PromatconMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_RangeFiveMember" name="RangeFiveMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_RangeFourMember" name="RangeFourMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_RangeThreeMember" name="RangeThreeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_RangeTwoMember" name="RangeTwoMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_ReferenceRateAxis" name="ReferenceRateAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_ReferenceRateDomain" name="ReferenceRateDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_RentalEquipmentNet" name="RentalEquipmentNet" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ngs_SalesRevenueGoodsNetAndRentalIncomeMember" name="SalesRevenueGoodsNetAndRentalIncomeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_ScheduleOfOtherLiabilitiesTable" name="ScheduleOfOtherLiabilitiesTable" nillable="true" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_ShareBasedCompensationArrangementByShareBasedPaymentAwardNumberofRemainingSharesAuthorized" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardNumberofRemainingSharesAuthorized" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="instant" />
  <xsd:element id="ngs_ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsNonvestedOptionsCancelledOrForfeitedNumberOfShares" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsNonvestedOptionsCancelledOrForfeitedNumberOfShares" nillable="true" substitutionGroup="xbrli:item" type="xbrli:sharesItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsNonvestedOptionsCancelledOrForfeitedWeightedAverageGrantDateFairValue" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsNonvestedOptionsCancelledOrForfeitedWeightedAverageGrantDateFairValue" nillable="true" substitutionGroup="xbrli:item" type="num:perShareItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsIntrinsicValueRollForward" name="ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsIntrinsicValueRollForward" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsWeightedAverageRemainingContractualTermAbstract" name="ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsWeightedAverageRemainingContractualTermAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_SharebasedCompensationArrangementbySharebasedPaymentAwardEquityInstrumentsOtherthanOptionsAggregateIntrinsicValueGrantsinPeriod" name="SharebasedCompensationArrangementbySharebasedPaymentAwardEquityInstrumentsOtherthanOptionsAggregateIntrinsicValueGrantsinPeriod" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ngs_SharebasedCompensationArrangementbySharebasedPaymentAwardOptionsForfeitedinPeriodIntrinsicValue" name="SharebasedCompensationArrangementbySharebasedPaymentAwardOptionsForfeitedinPeriodIntrinsicValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ngs_SharebasedCompensationArrangementbySharebasedPaymentAwardOptionsNumberofOptionsGranted" name="SharebasedCompensationArrangementbySharebasedPaymentAwardOptionsNumberofOptionsGranted" nillable="true" substitutionGroup="xbrli:item" type="xbrli:integerItemType" xbrli:periodType="duration" />
  <xsd:element id="ngs_TransferOfRentalEquipmentToInventory" name="TransferOfRentalEquipmentToInventory" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_TwoThousandNineRestrictedStockUnitsPlanMember" name="TwoThousandNineRestrictedStockUnitsPlanMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_VicePresidentofTechnicalServicesMember" name="VicePresidentofTechnicalServicesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ngs_WeightedAverageSharesOutstandingBasicAndDilutedAbstract" name="WeightedAverageSharesOutstandingBasicAndDilutedAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
</xsd:schema>
