<?xml version="1.0" encoding="UTF-8"?>

<!--XBRL Document Created with Wdesk from Workiva-->
<!--Copyright 2017 Workiva-->
<!--r:c5067941-b392-40f2-aac6-d3c0fb9bc81d,g:bb5f0a17-8beb-4c9b-98fa-ce0d91306251-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:ngs="http://naturalgaservices.com/20190331" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:link="http://www.xbrl.org/2003/linkbase" attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://naturalgaservices.com/20190331">
  <xs:import namespace="http://fasb.org/srt/2018-01-31" schemaLocation="http://xbrl.fasb.org/srt/2018/elts/srt-2018-01-31.xsd"/>
  <xs:import namespace="http://fasb.org/us-gaap/2018-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2018/elts/us-gaap-2018-01-31.xsd"/>
  <xs:import namespace="http://www.w3.org/1999/xlink" schemaLocation="http://www.xbrl.org/2003/xlink-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd"/>
  <xs:import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/dei/2018-01-31" schemaLocation="https://xbrl.sec.gov/dei/2018/dei-2018-01-31.xsd"/>
  <xs:element id="ngs_ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsWeightedAverageRemainingContractualTermAbstract" abstract="true" name="ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsWeightedAverageRemainingContractualTermAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ngs_DeferredCompensationArrangementwithIndividualMaximumAnnualContributionsPerEmployeePercent" abstract="false" name="DeferredCompensationArrangementwithIndividualMaximumAnnualContributionsPerEmployeePercent" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ngs_LineofCreditFacilityLeverageRatio" abstract="false" name="LineofCreditFacilityLeverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="ngs_RangeTwoMember" abstract="true" name="RangeTwoMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_FlaresRelatedMember" abstract="true" name="FlaresRelatedMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_CompressorRelatedMember" abstract="true" name="CompressorRelatedMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_VicePresidentofTechnicalServicesMember" abstract="true" name="VicePresidentofTechnicalServicesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_GenisHoldingsLLCMember" abstract="true" name="GenisHoldingsLLCMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_InventoryCurrentAndNoncurrentNet" abstract="false" name="InventoryCurrentAndNoncurrentNet" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_AntidilutiveEffectMember" abstract="true" name="AntidilutiveEffectMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleGeneralInventory" abstract="false" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleGeneralInventory" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ngs_EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsOutstandingRollForward" abstract="true" name="EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsOutstandingRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ngs_NGLLCMember" abstract="true" name="NGLLCMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsWeightedAverageGrantDateFairValueRollForward" abstract="true" name="EmployeeServiceShareBasedCompensationNonvestedAwardsStockOptionsWeightedAverageGrantDateFairValueRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ngs_TransferOfRentalEquipmentToInventory" abstract="false" name="TransferOfRentalEquipmentToInventory" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_AccountsReceivableExcludingContractsWithCustomerAssetCurrent" abstract="false" name="AccountsReceivableExcludingContractsWithCustomerAssetCurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_InventoryCurrentRawMaterialsNetofReserves" abstract="false" name="InventoryCurrentRawMaterialsNetofReserves" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityPotentialMaximumBorrowingCapacity" abstract="false" name="LineOfCreditFacilityPotentialMaximumBorrowingCapacity" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityReferenceRateNumberOfAllowableBorrowingsOutstanding" abstract="false" name="LineOfCreditFacilityReferenceRateNumberOfAllowableBorrowingsOutstanding" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="ngs_RangeOneMember" abstract="true" name="RangeOneMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_OperatingLeaseRightOfUseAssetAccumulatedAmortization" abstract="false" name="OperatingLeaseRightOfUseAssetAccumulatedAmortization" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineofCreditFacilityCommitmentCoverageRatio" abstract="false" name="LineofCreditFacilityCommitmentCoverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="ngs_OtherPartsRebuildsMember" abstract="true" name="OtherPartsRebuildsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_RentalMember" abstract="true" name="RentalMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_WeightedAverageSharesOutstandingBasicAndDilutedAbstract" abstract="true" name="WeightedAverageSharesOutstandingBasicAndDilutedAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ngs_ServiceandMaintenanceMember" abstract="true" name="ServiceandMaintenanceMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_CapitalizedContractCostsPolicyPolicyTextBlock" abstract="false" name="CapitalizedContractCostsPolicyPolicyTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ngs_AssetsAndLiabilitiesLesseeTableTextBlock" abstract="false" name="AssetsAndLiabilitiesLesseeTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ngs_ProceedsFromPurchaseCommitmentDiscountNet" abstract="false" name="ProceedsFromPurchaseCommitmentDiscountNet" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_CbFloatingRateMember" abstract="true" name="CbFloatingRateMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_InventoryValuationReservesDeductions" abstract="false" name="InventoryValuationReservesDeductions" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_DocumentAndEntityInformationAbstract" abstract="true" name="DocumentAndEntityInformationAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityDefaultTriggerCertainDefaultsOfOtherCompanyIndebtednessAmount" abstract="false" name="LineOfCreditFacilityDefaultTriggerCertainDefaultsOfOtherCompanyIndebtednessAmount" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityPotentialIncreaseInBorrowingCapacity" abstract="false" name="LineOfCreditFacilityPotentialIncreaseInBorrowingCapacity" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_IntangibleAssetsAccumulatedAmortization" abstract="false" name="IntangibleAssetsAccumulatedAmortization" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_RentalEquipmentNet" abstract="false" name="RentalEquipmentNet" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleEquipmentInventory" abstract="false" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleEquipmentInventory" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ngs_RangeFourMember" abstract="true" name="RangeFourMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_DeferredCompensationArrangementwithIndividualDeferredRestrictedStock" abstract="false" name="DeferredCompensationArrangementwithIndividualDeferredRestrictedStock" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="xbrli:sharesItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityAllowableShareOfTotalCommitmentAmountAttributableToGeneralInventoryComponent" abstract="false" name="LineOfCreditFacilityCurrentBorrowingCapacityAllowableShareOfTotalCommitmentAmountAttributableToGeneralInventoryComponent" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ngs_RangeThreeMember" abstract="true" name="RangeThreeMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsCanceledOrForfeitedInPeriodIntrinsicValue" abstract="false" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOptionsCanceledOrForfeitedInPeriodIntrinsicValue" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_InventoryNoncurrentRawMaterialsNetofReserves" abstract="false" name="InventoryNoncurrentRawMaterialsNetofReserves" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_TransferOfPrepaidsToRentalEquipmentAndInventory" abstract="false" name="TransferOfPrepaidsToRentalEquipmentAndInventory" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_SalesServiceLineMember" abstract="true" name="SalesServiceLineMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_BillAndHoldArrangementMember" abstract="true" name="BillAndHoldArrangementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityDefaultTriggerRenderingOfCertainJudgmentsAmount" abstract="false" name="LineOfCreditFacilityDefaultTriggerRenderingOfCertainJudgmentsAmount" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_ProductSalesMember" abstract="true" name="ProductSalesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ngs_LesseeOperatingLeaseRemainingLeaseTerm" abstract="false" name="LesseeOperatingLeaseRemainingLeaseTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="ngs_AccumulatedDepreciationRentalEquipment" abstract="false" name="AccumulatedDepreciationRentalEquipment" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ngs_LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleAccountsReceivable" abstract="false" name="LineOfCreditFacilityCurrentBorrowingCapacityComponentPercentageOfEligibleAccountsReceivable" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ngs_ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsIntrinsicValueRollForward" abstract="true" name="ShareBasedCompensationArrangementsByShareBasedPaymentAwardOptionsIntrinsicValueRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:annotation>
    <xs:appinfo>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20190331_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20190331_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20190331_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ngs-20190331_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple"/>
      <link:roleType id="DocumentandEntityInformation" roleURI="http://naturalgaservices.com/role/DocumentandEntityInformation">
        <link:definition>0001001 - 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="CondensedConsolidatedBalanceSheets" roleURI="http://naturalgaservices.com/role/CondensedConsolidatedBalanceSheets">
        <link:definition>1001002 - Statement - Condensed Consolidated 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="CondensedConsolidatedBalanceSheetsParentheticals" roleURI="http://naturalgaservices.com/role/CondensedConsolidatedBalanceSheetsParentheticals">
        <link:definition>1002003 - Statement - Condensed Consolidated Balance Sheets (Parentheticals)</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="CondensedConsolidatedIncomeStatements" roleURI="http://naturalgaservices.com/role/CondensedConsolidatedIncomeStatements">
        <link:definition>1003004 - Statement - Condensed Consolidated Income Statements</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="CondensedConsolidatedStatementsofStockholdersEquity" roleURI="http://naturalgaservices.com/role/CondensedConsolidatedStatementsofStockholdersEquity">
        <link:definition>1004005 - Statement - Condensed Consolidated 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="CondensedConsolidatedStatementsofCashFlows" roleURI="http://naturalgaservices.com/role/CondensedConsolidatedStatementsofCashFlows">
        <link:definition>1005006 - Statement - Condensed Consolidated 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="BasisofPresentationandSummaryofSignificantAccountingPolicies" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPolicies">
        <link:definition>2101101 - Disclosure - Basis of Presentation and 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="BasisofPresentationandSummaryofSignificantAccountingPoliciesPolicies" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesPolicies">
        <link:definition>2202201 - Disclosure - Basis of Presentation and 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="BasisofPresentationandSummaryofSignificantAccountingPoliciesTables" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesTables">
        <link:definition>2303301 - Disclosure - Basis of Presentation and 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>
      <link:roleType id="BasisofPresentationandSummaryofSignificantAccountingPoliciesNarrativeDetails" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesNarrativeDetails">
        <link:definition>2404401 - Disclosure - Basis of Presentation and 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="BasisofPresentationandSummaryofSignificantAccountingPoliciesDisaggregationofRevenueDetails" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesDisaggregationofRevenueDetails">
        <link:definition>2405402 - Disclosure - Basis of Presentation and Summary of Significant Accounting Policies (Disaggregation of Revenue) (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="BasisofPresentationandSummaryofSignificantAccountingPoliciesContractBalancesDetails" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesContractBalancesDetails">
        <link:definition>2406403 - Disclosure - Basis of Presentation and Summary of Significant Accounting Policies (Contract Balances) (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="BasisofPresentationandSummaryofSignificantAccountingPoliciesCumulativeEffectofChangesfromAdoptionofASUDetails" roleURI="http://naturalgaservices.com/role/BasisofPresentationandSummaryofSignificantAccountingPoliciesCumulativeEffectofChangesfromAdoptionofASUDetails">
        <link:definition>2407404 - Disclosure - Basis of Presentation and Summary of Significant Accounting Policies (Cumulative Effect of Changes from Adoption of ASU) (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="StockBasedCompensation" roleURI="http://naturalgaservices.com/role/StockBasedCompensation">
        <link:definition>2108102 - 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="StockBasedCompensationTables" roleURI="http://naturalgaservices.com/role/StockBasedCompensationTables">
        <link:definition>2309302 - 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="StockBasedCompensationStockOptionActivityDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationStockOptionActivityDetails">
        <link:definition>2410405 - 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="StockBasedCompensationStockOptionsOutstandingDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationStockOptionsOutstandingDetails">
        <link:definition>2411406 - Disclosure - Stock-Based Compensation (Stock Options Outstanding) (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>2412407 - 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="StockBasedCompensationRestrictedStockDetails" roleURI="http://naturalgaservices.com/role/StockBasedCompensationRestrictedStockDetails">
        <link:definition>2413408 - Disclosure - Stock-Based Compensation (Restricted Stock) (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="Inventory" roleURI="http://naturalgaservices.com/role/Inventory">
        <link:definition>2114103 - Disclosure - Inventory</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="InventoryTables" roleURI="http://naturalgaservices.com/role/InventoryTables">
        <link:definition>2315303 - Disclosure - Inventory (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="InventoryDetails" roleURI="http://naturalgaservices.com/role/InventoryDetails">
        <link:definition>2416409 - Disclosure - Inventory (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="DeferredCompensationPlans" roleURI="http://naturalgaservices.com/role/DeferredCompensationPlans">
        <link:definition>2117104 - Disclosure - Deferred Compensation Plans</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="DeferredCompensationPlansDetails" roleURI="http://naturalgaservices.com/role/DeferredCompensationPlansDetails">
        <link:definition>2418410 - Disclosure - Deferred Compensation Plans (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="CreditFacility" roleURI="http://naturalgaservices.com/role/CreditFacility">
        <link:definition>2119105 - 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>2420411 - 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="Leases" roleURI="http://naturalgaservices.com/role/Leases">
        <link:definition>2121106 - Disclosure - Leases</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="LeasesTables" roleURI="http://naturalgaservices.com/role/LeasesTables">
        <link:definition>2322304 - Disclosure - Leases (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="LeasesNarrativeDetails" roleURI="http://naturalgaservices.com/role/LeasesNarrativeDetails">
        <link:definition>2423412 - Disclosure - Leases (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="LeasesBalanceSheetImpactDetails" roleURI="http://naturalgaservices.com/role/LeasesBalanceSheetImpactDetails">
        <link:definition>2424413 - Disclosure - Leases (Balance Sheet Impact) (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="LeasesCashFlowImpactDetails" roleURI="http://naturalgaservices.com/role/LeasesCashFlowImpactDetails">
        <link:definition>2425414 - Disclosure - Leases (Cash Flow Impact) (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="LeasesFutureMaturitiesofLeaseLiabilitiesDetails" roleURI="http://naturalgaservices.com/role/LeasesFutureMaturitiesofLeaseLiabilitiesDetails">
        <link:definition>2426415 - Disclosure - Leases (Future Maturities of Lease 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="LeasesFutureMaturitiesofLeaseLiabilitiesDetails_1" roleURI="http://naturalgaservices.com/role/LeasesFutureMaturitiesofLeaseLiabilitiesDetails_1">
        <link:definition>2426415 - Disclosure - Leases (Future Maturities of Lease 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="LeasesFutureMinimumObligationsUnderLeaseCommitmentsDetails" roleURI="http://naturalgaservices.com/role/LeasesFutureMinimumObligationsUnderLeaseCommitmentsDetails">
        <link:definition>2427416 - Disclosure - Leases (Future Minimum Obligations Under Lease Commitments) (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="EarningsperShare" roleURI="http://naturalgaservices.com/role/EarningsperShare">
        <link:definition>2128107 - Disclosure - Earnings per Share</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="EarningsperShareTables" roleURI="http://naturalgaservices.com/role/EarningsperShareTables">
        <link:definition>2329305 - Disclosure - Earnings per Share (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="EarningsperShareBasicandDilutedDetails" roleURI="http://naturalgaservices.com/role/EarningsperShareBasicandDilutedDetails">
        <link:definition>2430417 - Disclosure - Earnings per Share (Basic and Diluted) (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="SegmentInformation" roleURI="http://naturalgaservices.com/role/SegmentInformation">
        <link:definition>2131108 - Disclosure - Segment 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="SegmentInformationTables" roleURI="http://naturalgaservices.com/role/SegmentInformationTables">
        <link:definition>2332306 - Disclosure - Segment Information (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="SegmentInformationDetails" roleURI="http://naturalgaservices.com/role/SegmentInformationDetails">
        <link:definition>2433418 - Disclosure - Segment Information (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="CommitmentsandContingencies" roleURI="http://naturalgaservices.com/role/CommitmentsandContingencies">
        <link:definition>2134109 - 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="CommitmentsandContingenciesDetails" roleURI="http://naturalgaservices.com/role/CommitmentsandContingenciesDetails">
        <link:definition>2435419 - Disclosure - Commitments and Contingencies (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="RelatedParty" roleURI="http://naturalgaservices.com/role/RelatedParty">
        <link:definition>2136110 - Disclosure - Related Party</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="RelatedPartyNarrativeDetails" roleURI="http://naturalgaservices.com/role/RelatedPartyNarrativeDetails">
        <link:definition>2437420 - Disclosure - Related Party (Narrative) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xs:appinfo>
  </xs:annotation>
</xs:schema>
