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

<!--XBRL Document Created with Wdesk from Workiva-->
<!--Copyright 2020 Workiva-->
<!--r:8d8020bc-ff7b-405c-8202-ec7ab330229c,g:2187a132-9a85-4e46-b255-4198b6db0f69-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:ns="http://www.nustarenergy.com/20200930" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:num="http://www.xbrl.org/dtr/type/numeric" attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.nustarenergy.com/20200930">
  <xs:import namespace="http://fasb.org/srt/2020-01-31" schemaLocation="http://xbrl.fasb.org/srt/2020/elts/srt-2020-01-31.xsd"/>
  <xs:import namespace="http://fasb.org/us-gaap/2020-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2020/elts/us-gaap-2020-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.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/dei/2020-01-31" schemaLocation="https://xbrl.sec.gov/dei/2020/dei-2020-01-31.xsd"/>
  <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="ns-20200930_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="ns-20200930_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="ns-20200930_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="ns-20200930_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple"/>
      <link:roleType id="DEIDocument" roleURI="http://www.nustarenergy.com/role/DEIDocument">
        <link:definition>0001001 - Document - DEI Document</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="CONSOLIDATEDBALANCESHEETS" roleURI="http://www.nustarenergy.com/role/CONSOLIDATEDBALANCESHEETS">
        <link:definition>1001002 - Statement - 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="CONSOLIDATEDBALANCESHEETSparenthetical" roleURI="http://www.nustarenergy.com/role/CONSOLIDATEDBALANCESHEETSparenthetical">
        <link:definition>1002003 - Statement - CONSOLIDATED 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="CONDENSEDCONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOMELOSS" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOMELOSS">
        <link:definition>1003004 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF COMPREHENSIVE INCOME (LOSS)</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="CONSOLIDATEDSTATEMENTSOFCASHFLOWS" roleURI="http://www.nustarenergy.com/role/CONSOLIDATEDSTATEMENTSOFCASHFLOWS">
        <link:definition>1004005 - Statement - 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="CONSOLIDATEDSTATEMENTSOFPARTNERSEQUITYANDMEZZANINEEQUITY" roleURI="http://www.nustarenergy.com/role/CONSOLIDATEDSTATEMENTSOFPARTNERSEQUITYANDMEZZANINEEQUITY">
        <link:definition>1005006 - Statement - CONSOLIDATED STATEMENTS OF PARTNERS' EQUITY AND MEZZANINE 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="CONSOLIDATEDSTATEMENTSOFPARTNERSEQUITYANDMEZZANINEEQUITYParenthetical" roleURI="http://www.nustarenergy.com/role/CONSOLIDATEDSTATEMENTSOFPARTNERSEQUITYANDMEZZANINEEQUITYParenthetical">
        <link:definition>1006007 - Statement - CONSOLIDATED STATEMENTS OF PARTNERS' EQUITY AND MEZZANINE EQUITY (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="ORGANIZATIONANDBASISOFPRESENTATION" roleURI="http://www.nustarenergy.com/role/ORGANIZATIONANDBASISOFPRESENTATION">
        <link:definition>2101101 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION</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="ORGANIZATIONANDBASISOFPRESENTATIONNarrative1Details" roleURI="http://www.nustarenergy.com/role/ORGANIZATIONANDBASISOFPRESENTATIONNarrative1Details">
        <link:definition>2402401 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION Narrative 1 (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="ORGANIZATIONANDBASISOFPRESENTATIONNarrative2Details" roleURI="http://www.nustarenergy.com/role/ORGANIZATIONANDBASISOFPRESENTATIONNarrative2Details">
        <link:definition>2403402 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION Narrative 2 (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="ORGANIZATIONANDBASISOFPRESENTATIONNarrative3Details" roleURI="http://www.nustarenergy.com/role/ORGANIZATIONANDBASISOFPRESENTATIONNarrative3Details">
        <link:definition>2404403 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION Narrative 3 (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="NEWACCOUNTINGPRONOUNCEMENTS" roleURI="http://www.nustarenergy.com/role/NEWACCOUNTINGPRONOUNCEMENTS">
        <link:definition>2105102 - Disclosure - NEW ACCOUNTING PRONOUNCEMENTS</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="IMPAIRMENTSANDDISCONTINUEDOPERATIONS" roleURI="http://www.nustarenergy.com/role/IMPAIRMENTSANDDISCONTINUEDOPERATIONS">
        <link:definition>2106103 - Disclosure - IMPAIRMENTS AND DISCONTINUED OPERATIONS</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="IMPAIRMENTSANDDISCONTINUEDOPERATIONSTables" roleURI="http://www.nustarenergy.com/role/IMPAIRMENTSANDDISCONTINUEDOPERATIONSTables">
        <link:definition>2307301 - Disclosure - IMPAIRMENTS AND DISCONTINUED OPERATIONS (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="IMPAIRMENTSANDDISCONTINUEDOPERATIONSNarrativeDetails" roleURI="http://www.nustarenergy.com/role/IMPAIRMENTSANDDISCONTINUEDOPERATIONSNarrativeDetails">
        <link:definition>2408404 - Disclosure - IMPAIRMENTS AND DISCONTINUED OPERATIONS 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="IMPAIRMENTSANDDISCONTINUEDOPERATIONSTable1Details" roleURI="http://www.nustarenergy.com/role/IMPAIRMENTSANDDISCONTINUEDOPERATIONSTable1Details">
        <link:definition>2409405 - Disclosure - IMPAIRMENTS AND DISCONTINUED OPERATIONS Table 1 (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="IMPAIRMENTSANDDISCONTINUEDOPERATIONSTable2Details" roleURI="http://www.nustarenergy.com/role/IMPAIRMENTSANDDISCONTINUEDOPERATIONSTable2Details">
        <link:definition>2410406 - Disclosure - IMPAIRMENTS AND DISCONTINUED OPERATIONS Table 2 (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="REVENUEFROMCONTRACTSWITHCUSTOMERS" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERS">
        <link:definition>2111104 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS</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="REVENUEFROMCONTRACTSWITHCUSTOMERSTables" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSTables">
        <link:definition>2312302 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS (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="REVENUEFROMCONTRACTSWITHCUSTOMERSTable1ContractAssetsandLiabilitiesDetails" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSTable1ContractAssetsandLiabilitiesDetails">
        <link:definition>2413407 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS Table 1 - Contract 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="REVENUEFROMCONTRACTSWITHCUSTOMERSNarrativeDetails" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSNarrativeDetails">
        <link:definition>2414408 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS 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="REVENUEFROMCONTRACTSWITHCUSTOMERSTable2ExpectedTimingofSatisfactionofPerformanceObligationsDetails" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSTable2ExpectedTimingofSatisfactionofPerformanceObligationsDetails">
        <link:definition>2415409 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS Table 2 - Expected Timing of Satisfaction of Performance Obligations (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="REVENUEFROMCONTRACTSWITHCUSTOMERSTable2ExpectedTimingofSatisfactionofPerformanceObligationsDetails_1" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSTable2ExpectedTimingofSatisfactionofPerformanceObligationsDetails_1">
        <link:definition>2415409 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS Table 2 - Expected Timing of Satisfaction of Performance Obligations (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="REVENUEFROMCONTRACTSWITHCUSTOMERSTable3DisaggregationofRevenuesDetails" roleURI="http://www.nustarenergy.com/role/REVENUEFROMCONTRACTSWITHCUSTOMERSTable3DisaggregationofRevenuesDetails">
        <link:definition>2416410 - Disclosure - REVENUE FROM CONTRACTS WITH CUSTOMERS Table 3 - Disaggregation of Revenues (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="DEBT" roleURI="http://www.nustarenergy.com/role/DEBT">
        <link:definition>2117105 - Disclosure - DEBT</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="DEBTTables" roleURI="http://www.nustarenergy.com/role/DEBTTables">
        <link:definition>2318303 - Disclosure - DEBT (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="DEBTNarrative1Details" roleURI="http://www.nustarenergy.com/role/DEBTNarrative1Details">
        <link:definition>2419411 - Disclosure - DEBT Narrative 1 (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="DEBTNarrative2Details" roleURI="http://www.nustarenergy.com/role/DEBTNarrative2Details">
        <link:definition>2420412 - Disclosure - DEBT Narrative 2 (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="DEBTGoZoneBondsTableDetails" roleURI="http://www.nustarenergy.com/role/DEBTGoZoneBondsTableDetails">
        <link:definition>2421413 - Disclosure - DEBT GoZone Bonds Table (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="DEBTNarrative3Details" roleURI="http://www.nustarenergy.com/role/DEBTNarrative3Details">
        <link:definition>2422414 - Disclosure - DEBT Narrative 3 (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://www.nustarenergy.com/role/COMMITMENTSANDCONTINGENCIES">
        <link:definition>2123106 - 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="COMMITMENTSANDCONTINGENCIESNarrativeDetails" roleURI="http://www.nustarenergy.com/role/COMMITMENTSANDCONTINGENCIESNarrativeDetails">
        <link:definition>2424415 - 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="DERIVATIVESANDFAIRVALUEMEASUREMENTS" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTS">
        <link:definition>2125107 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS</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="DERIVATIVESANDFAIRVALUEMEASUREMENTSTables" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTSTables">
        <link:definition>2326304 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS (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="DERIVATIVESANDFAIRVALUEMEASUREMENTSNarrative1Details" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTSNarrative1Details">
        <link:definition>2427416 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS Narrative 1 (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="DERIVATIVESANDFAIRVALUEMEASUREMENTSTable1ImpactofDerivativesonEarningsDetails" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTSTable1ImpactofDerivativesonEarningsDetails">
        <link:definition>2428417 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS Table 1 - Impact of Derivatives on Earnings (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="DERIVATIVESANDFAIRVALUEMEASUREMENTSNarrative2Details" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTSNarrative2Details">
        <link:definition>2429418 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS Narrative 2 (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="DERIVATIVESANDFAIRVALUEMEASUREMENTSTable2EstimatedFairValuesandCarryingAmountsofLongTermDebtDetails" roleURI="http://www.nustarenergy.com/role/DERIVATIVESANDFAIRVALUEMEASUREMENTSTable2EstimatedFairValuesandCarryingAmountsofLongTermDebtDetails">
        <link:definition>2430419 - Disclosure - DERIVATIVES AND FAIR VALUE MEASUREMENTS Table 2 - Estimated Fair Values and Carrying Amounts of Long-Term Debt (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="SERIESDCUMULATIVECONVERTIBLEPREFERREDUNITS" roleURI="http://www.nustarenergy.com/role/SERIESDCUMULATIVECONVERTIBLEPREFERREDUNITS">
        <link:definition>2131108 - Disclosure - SERIES D CUMULATIVE CONVERTIBLE PREFERRED UNITS</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="SERIESDCUMULATIVECONVERTIBLEPREFERREDUNITSNarrativeDetails" roleURI="http://www.nustarenergy.com/role/SERIESDCUMULATIVECONVERTIBLEPREFERREDUNITSNarrativeDetails">
        <link:definition>2432420 - Disclosure - SERIES D CUMULATIVE CONVERTIBLE PREFERRED UNITS 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="PARTNERSEQUITY" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITY">
        <link:definition>2133109 - Disclosure - PARTNERS' 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="PARTNERSEQUITYTables" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITYTables">
        <link:definition>2334305 - Disclosure - PARTNERS' EQUITY (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="PARTNERSEQUITYTable1CashDistributionsPreferredUnitsDetails" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITYTable1CashDistributionsPreferredUnitsDetails">
        <link:definition>2435421 - Disclosure - PARTNERS' EQUITY Table 1 - Cash Distributions - Preferred Units (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="PARTNERSEQUITYNarrativeDetails" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITYNarrativeDetails">
        <link:definition>2436422 - Disclosure - PARTNERS' EQUITY 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="PARTNERSEQUITYTable2CashDistributionsDeclaredCommonLimitedPartnersDetails" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITYTable2CashDistributionsDeclaredCommonLimitedPartnersDetails">
        <link:definition>2437423 - Disclosure - PARTNERS' EQUITY Table 2 - Cash Distributions Declared - Common Limited Partners (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="PARTNERSEQUITYTable3BalanceofandChangesinAccumulatedOtherComprehensiveIncomeLossDetails" roleURI="http://www.nustarenergy.com/role/PARTNERSEQUITYTable3BalanceofandChangesinAccumulatedOtherComprehensiveIncomeLossDetails">
        <link:definition>2438424 - Disclosure - PARTNERS' EQUITY Table 3 - Balance of and Changes in Accumulated Other Comprehensive Income (Loss) (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="NETLOSSINCOMEPERCOMMONUNIT" roleURI="http://www.nustarenergy.com/role/NETLOSSINCOMEPERCOMMONUNIT">
        <link:definition>2139110 - Disclosure - NET (LOSS) INCOME PER COMMON UNIT</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="NETLOSSINCOMEPERCOMMONUNITTables" roleURI="http://www.nustarenergy.com/role/NETLOSSINCOMEPERCOMMONUNITTables">
        <link:definition>2340306 - Disclosure - NET (LOSS) INCOME PER COMMON UNIT (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="NETLOSSINCOMEPERCOMMONUNITTableNetIncomeLossperCommonUnitDetails" roleURI="http://www.nustarenergy.com/role/NETLOSSINCOMEPERCOMMONUNITTableNetIncomeLossperCommonUnitDetails">
        <link:definition>2441425 - Disclosure - NET (LOSS) INCOME PER COMMON UNIT Table - Net Income (Loss) per Common Unit (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="SUPPLEMENTALCASHFLOWINFORMATION" roleURI="http://www.nustarenergy.com/role/SUPPLEMENTALCASHFLOWINFORMATION">
        <link:definition>2142111 - Disclosure - SUPPLEMENTAL CASH FLOW 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="SUPPLEMENTALCASHFLOWINFORMATIONTables" roleURI="http://www.nustarenergy.com/role/SUPPLEMENTALCASHFLOWINFORMATIONTables">
        <link:definition>2343307 - Disclosure - SUPPLEMENTAL CASH FLOW 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="SUPPLEMENTALCASHFLOWINFORMATIONTable1ChangesinCurrentAssetsandLiabilitiesDetails" roleURI="http://www.nustarenergy.com/role/SUPPLEMENTALCASHFLOWINFORMATIONTable1ChangesinCurrentAssetsandLiabilitiesDetails">
        <link:definition>2444426 - Disclosure - SUPPLEMENTAL CASH FLOW INFORMATION - Table 1 - Changes in Current 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="SUPPLEMENTALCASHFLOWINFORMATIONTable2CashFlowsRelatedtoInterestandIncomeTaxesDetails" roleURI="http://www.nustarenergy.com/role/SUPPLEMENTALCASHFLOWINFORMATIONTable2CashFlowsRelatedtoInterestandIncomeTaxesDetails">
        <link:definition>2445427 - Disclosure - SUPPLEMENTAL CASH FLOW INFORMATION - Table 2 - Cash Flows Related to Interest and 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="SUPPLEMENTALCASHFLOWINFORMATIONTable3ScheduleofCashCashEquivalentsandRestrictedCashDetails" roleURI="http://www.nustarenergy.com/role/SUPPLEMENTALCASHFLOWINFORMATIONTable3ScheduleofCashCashEquivalentsandRestrictedCashDetails">
        <link:definition>2446428 - Disclosure - SUPPLEMENTAL CASH FLOW INFORMATION - Table 3 - Schedule of Cash, Cash Equivalents and Restricted Cash (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://www.nustarenergy.com/role/SEGMENTINFORMATION">
        <link:definition>2147112 - 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://www.nustarenergy.com/role/SEGMENTINFORMATIONTables">
        <link:definition>2348308 - 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="SEGMENTINFORMATIONTable1ResultsofOperationsDetails" roleURI="http://www.nustarenergy.com/role/SEGMENTINFORMATIONTable1ResultsofOperationsDetails">
        <link:definition>2449429 - Disclosure - SEGMENT INFORMATION Table 1 - Results of Operations (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="SEGMENTINFORMATIONTable2AssetsbyReportableSegmentDetails" roleURI="http://www.nustarenergy.com/role/SEGMENTINFORMATIONTable2AssetsbyReportableSegmentDetails">
        <link:definition>2450430 - Disclosure - SEGMENT INFORMATION Table 2 - Assets by Reportable Segment (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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTS" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTS">
        <link:definition>2151113 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL 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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTables" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTables">
        <link:definition>2352309 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS (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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSNarrativeDetails" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSNarrativeDetails">
        <link:definition>2453431 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS 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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable1CondensedConsolidatingBalanceSheetsDetails" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable1CondensedConsolidatingBalanceSheetsDetails">
        <link:definition>2454432 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS Table 1 - Condensed Consolidating Balance Sheets (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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable2CondensedConsolidatingStatementsofComprehensiveIncomeDetails" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable2CondensedConsolidatingStatementsofComprehensiveIncomeDetails">
        <link:definition>2455433 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS Table 2 - Condensed Consolidating Statements of Comprehensive Income (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="CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable3CondensedConsolidatingStatementsofCashFlowsDetails" roleURI="http://www.nustarenergy.com/role/CONDENSEDCONSOLIDATINGFINANCIALSTATEMENTSTable3CondensedConsolidatingStatementsofCashFlowsDetails">
        <link:definition>2456434 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS Table 3 - Condensed Consolidating Statements of Cash Flows (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="SUBSEQUENTEVENTS" roleURI="http://www.nustarenergy.com/role/SUBSEQUENTEVENTS">
        <link:definition>2157114 - Disclosure - SUBSEQUENT EVENTS</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="SUBSEQUENTEVENTSTables" roleURI="http://www.nustarenergy.com/role/SUBSEQUENTEVENTSTables">
        <link:definition>2358310 - Disclosure - SUBSEQUENT EVENTS (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="SUBSEQUENTEVENTSDetails" roleURI="http://www.nustarenergy.com/role/SUBSEQUENTEVENTSDetails">
        <link:definition>2459435 - Disclosure - SUBSEQUENT EVENTS (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:element id="ns_InvestmentInSubsidiaries" abstract="false" name="InvestmentInSubsidiaries" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_DisposalGroupIncludingDiscontinuedOperationCostOfRevenues" abstract="false" name="DisposalGroupIncludingDiscontinuedOperationCostOfRevenues" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_NustarEnergyLpMember" abstract="true" name="NustarEnergyLpMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_InvestmentInWhollyOwnedSubsidiaries" abstract="false" name="InvestmentInWhollyOwnedSubsidiaries" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_RepaymentOfDebtAndPaymentForExtinguishmentCosts" abstract="false" name="RepaymentOfDebtAndPaymentForExtinguishmentCosts" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_MezzanineEquityDisclosureTextBlock" abstract="false" name="MezzanineEquityDisclosureTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ns_DescriptionOfAssetsSold" abstract="false" name="DescriptionOfAssetsSold" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ns_TheSt.EustatiusDispositionMember" abstract="true" name="TheSt.EustatiusDispositionMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_UnsecuredTermLoanCreditAgreementMember" abstract="true" name="UnsecuredTermLoanCreditAgreementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_St.EustatiusBunkersMember" abstract="true" name="St.EustatiusBunkersMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_SeriesDPreferredLimitedPartnerMember" abstract="true" name="SeriesDPreferredLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_DepreciationDepletionAndAmortizationFromContinuingAndDiscontinuedOperations" abstract="false" name="DepreciationDepletionAndAmortizationFromContinuingAndDiscontinuedOperations" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_CommonLimitedPartnerDistribution" abstract="false" name="CommonLimitedPartnerDistribution" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_DisposalGroupIncludingDiscontinuedOperationTotalExpenses" abstract="false" name="DisposalGroupIncludingDiscontinuedOperationTotalExpenses" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_CondensedConsolidatingFinancialStatementsAbstract" abstract="true" name="CondensedConsolidatingFinancialStatementsAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ns_NumberofDaysWithinWhichDistributionIsPaidToCommonUnitholders" abstract="false" name="NumberofDaysWithinWhichDistributionIsPaidToCommonUnitholders" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="ns_StorageSegmentMember" abstract="true" name="StorageSegmentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PartnersCapitalOtherIncludingTemporaryEquity" abstract="false" name="PartnersCapitalOtherIncludingTemporaryEquity" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_EpuDistributionsLessThanGreaterThanEarnings" abstract="false" name="EpuDistributionsLessThanGreaterThanEarnings" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_RepaymentOfTermLoanAndPaymentForExtinguishmentCosts" abstract="false" name="RepaymentOfTermLoanAndPaymentForExtinguishmentCosts" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_DebtExtinguishmentCostsTypeDomain" abstract="true" name="DebtExtinguishmentCostsTypeDomain" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_NustarPipelineOperatingPartnershipLpMember" abstract="true" name="NustarPipelineOperatingPartnershipLpMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_InterestRateSwapsInterestRateReceived" abstract="false" name="InterestRateSwapsInterestRateReceived" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="ns_LogisticsRevolvingCreditAgreementMember" abstract="true" name="LogisticsRevolvingCreditAgreementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_EarlyRepaymentPremiumsMember" abstract="true" name="EarlyRepaymentPremiumsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_FuelsMarketingSegmentMember" abstract="true" name="FuelsMarketingSegmentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveJune292018toJune282020Member" abstract="true" name="PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveJune292018toJune282020Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_IntercompanyReceivable" abstract="false" name="IntercompanyReceivable" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_CommonLimitedPartnerMember" abstract="true" name="CommonLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveAxis" abstract="true" name="PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveAxis" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType"/>
  <xs:element id="ns_GoZoneBondsDueAugust2041Member" abstract="true" name="GoZoneBondsDueAugust2041Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_LogisticsNotesDue2020Member" abstract="true" name="LogisticsNotesDue2020Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveJune292020toJune282023Member" abstract="true" name="PreferredStockDistributionsPeriodDuringWhichRateIsEffectiveJune292020toJune282023Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ContributionsFromDistributionsToAffiliates" abstract="false" name="ContributionsFromDistributionsToAffiliates" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_NetIntercompanyBorrowingsRepayments" abstract="false" name="NetIntercompanyBorrowingsRepayments" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_GoZoneBondsDueDecember2040Member" abstract="true" name="GoZoneBondsDueDecember2040Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_LogisticsNotesDue2025Member" abstract="true" name="LogisticsNotesDue2025Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PetroleosdeVenezuelaS.A.PDVSAMember" abstract="true" name="PetroleosdeVenezuelaS.A.PDVSAMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_UnamortizedDebtIssuanceCostsUnamortizedDiscountAndCommitmentFeeMember" abstract="true" name="UnamortizedDebtIssuanceCostsUnamortizedDiscountAndCommitmentFeeMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_NumberOfTerminals" abstract="false" name="NumberOfTerminals" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="ns_OriginalIssueDiscount" abstract="false" name="OriginalIssueDiscount" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ns_DistributionPaymentDate" abstract="false" name="DistributionPaymentDate" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:dateItemType"/>
  <xs:element id="ns_ChangeinContractwithCustomerAssetTotal" abstract="false" name="ChangeinContractwithCustomerAssetTotal" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_NetIncomeLossExcludingPortionAttributableToTemporaryEquity" abstract="false" name="NetIncomeLossExcludingPortionAttributableToTemporaryEquity" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_AssetsHeldforSaleMember" abstract="true" name="AssetsHeldforSaleMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_CrudeOilPipelinesMember" abstract="true" name="CrudeOilPipelinesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ProceedsFromPaymentsForTerminationOfInterestRateSwaps" abstract="false" name="ProceedsFromPaymentsForTerminationOfInterestRateSwaps" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_EpuDistributionsLessThanGreaterThanEarningsAllocatedToLimitedPartners" abstract="false" name="EpuDistributionsLessThanGreaterThanEarningsAllocatedToLimitedPartners" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_ProceedsFromPaymentsForOtherFinancingActivitiesCondensedFinancialStatements" abstract="false" name="ProceedsFromPaymentsForOtherFinancingActivitiesCondensedFinancialStatements" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_NustarLogisticsLpMember" abstract="true" name="NustarLogisticsLpMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_DisposalGroupIncludingDiscontinuedOperationImpairmentLosses" abstract="false" name="DisposalGroupIncludingDiscontinuedOperationImpairmentLosses" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_GoZoneBondsDueJuly2040Member" abstract="true" name="GoZoneBondsDueJuly2040Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredStockDistributionsPeriodPeriodDuringWhichRateIsEffectiveJune292023andthereafterMember" abstract="true" name="PreferredStockDistributionsPeriodPeriodDuringWhichRateIsEffectiveJune292023andthereafterMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PipelineSegmentMember" abstract="true" name="PipelineSegmentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_SeriesCPreferredLimitedPartnerMember" abstract="true" name="SeriesCPreferredLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_DebtExtinguishmentCostsTypeAxis" abstract="true" name="DebtExtinguishmentCostsTypeAxis" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType"/>
  <xs:element id="ns_ContractwithCustomerLiabilityAdditions" abstract="false" name="ContractwithCustomerLiabilityAdditions" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_LiabilitiesHeldforSaleMember" abstract="true" name="LiabilitiesHeldforSaleMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ScheduleOfGoZoneBondsTableTextBlock" abstract="false" name="ScheduleOfGoZoneBondsTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ns_GoZoneBondsDueOctober2040Member" abstract="true" name="GoZoneBondsDueOctober2040Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_SelbyCaliforniaFireMember" abstract="true" name="SelbyCaliforniaFireMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PercentOfAvailableCashDistributed" abstract="false" name="PercentOfAvailableCashDistributed" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="num:percentItemType"/>
  <xs:element id="ns_StorageTerminalMember" abstract="true" name="StorageTerminalMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ThroughputTerminalMember" abstract="true" name="ThroughputTerminalMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_IncreaseDecreaseinAccountsPayableRelatedtoCapitalExpenditures" abstract="false" name="IncreaseDecreaseinAccountsPayableRelatedtoCapitalExpenditures" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_SeriesBPreferredLimitedPartnerMember" abstract="true" name="SeriesBPreferredLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_RefinedProductsandAmmoniaPipelinesMember" abstract="true" name="RefinedProductsandAmmoniaPipelinesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_DerivativeNotionalAmountTerminated" abstract="false" name="DerivativeNotionalAmountTerminated" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_DiscontinuedOperationsSupplementalIncomeStatementDisclosuresTableTextBlock" abstract="false" name="DiscontinuedOperationsSupplementalIncomeStatementDisclosuresTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ns_BusinessInterruptionLossfromSelbyCaliforniaFireMember" abstract="true" name="BusinessInterruptionLossfromSelbyCaliforniaFireMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_GoZoneBondsDueJune2038Member" abstract="true" name="GoZoneBondsDueJune2038Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_IntercompanyPayable" abstract="false" name="IntercompanyPayable" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_EPUCommonLimitedPartnerAllocation" abstract="false" name="EPUCommonLimitedPartnerAllocation" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_ContractWithCustomerAssetTransferToRevenues" abstract="false" name="ContractWithCustomerAssetTransferToRevenues" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_ContractwithCustomerAssetAdditions" abstract="false" name="ContractwithCustomerAssetAdditions" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_SeriesAPreferredLimitedPartnerMember" abstract="true" name="SeriesAPreferredLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_IncomeLossFromDiscontinuedOperationsNetOfTaxMember" abstract="true" name="IncomeLossFromDiscontinuedOperationsNetOfTaxMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_LogisticsNotesDue2030Member" abstract="true" name="LogisticsNotesDue2030Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_DiscontinuedOperationsSelectedCashFlowInformationTableTextBlock" abstract="false" name="DiscontinuedOperationsSelectedCashFlowInformationTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType"/>
  <xs:element id="ns_GozoneBondsMember" abstract="true" name="GozoneBondsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredLimitedPartnerDistribution" abstract="false" name="PreferredLimitedPartnerDistribution" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_PreferredLimitedPartnerMember" abstract="true" name="PreferredLimitedPartnerMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PreferredStockDistributionsPeriodDomain" abstract="true" name="PreferredStockDistributionsPeriodDomain" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_AmendedReceivablesFinancingAgreementMember" abstract="true" name="AmendedReceivablesFinancingAgreementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ChangeinContractwithCustomerLiabilityTotal" abstract="false" name="ChangeinContractwithCustomerLiabilityTotal" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_PreferredStockDividendAmountPerUnitPerDistributionPeriod" abstract="false" name="PreferredStockDividendAmountPerUnitPerDistributionPeriod" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="num:perShareItemType"/>
  <xs:element id="ns_PreferredStockAccretionofRedemptionDiscountIncludingTemporaryEquity" abstract="false" name="PreferredStockAccretionofRedemptionDiscountIncludingTemporaryEquity" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_SharebasedPaymentArrangementAmortization" abstract="false" name="SharebasedPaymentArrangementAmortization" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_TexasCityTXOwnershipInterestMember" abstract="true" name="TexasCityTXOwnershipInterestMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_ParentCompanyGuarantorMember" abstract="true" name="ParentCompanyGuarantorMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="nonnum:domainItemType"/>
  <xs:element id="ns_PartnersCapitalandTemporaryEquity" abstract="false" name="PartnersCapitalandTemporaryEquity" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="ns_MinimumPerUnitCashDividendRequiredToPermitDividendInKind" abstract="false" name="MinimumPerUnitCashDividendRequiredToPermitDividendInKind" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="num:perShareItemType"/>
</xs:schema>
</XBRL>
