<XBRL>
<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with WebFilings-->
<!-- -->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.nustarenergy.com/20140331" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:ns="http://www.nustarenergy.com/20140331" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <xsd:import namespace="http://fasb.org/us-gaap/2013-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2013/elts/us-gaap-2013-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2013-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2013/elts/us-roles-2013-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2013-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2013/elts/us-types-2013-01-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/arcrole/fact-explanatoryFact" schemaLocation="http://www.xbrl.org/lrr/arcrole/factExplanatory-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd" />
  <xsd:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/country/2013-01-31" schemaLocation="http://xbrl.sec.gov/country/2013/country-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2012-01-31" schemaLocation="http://xbrl.sec.gov/currency/2012/currency-2012-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2013-01-31" schemaLocation="http://xbrl.sec.gov/dei/2013/dei-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2013-01-31" schemaLocation="http://xbrl.sec.gov/exch/2013/exch-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2013-01-31" schemaLocation="http://xbrl.sec.gov/invest/2013/invest-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/naics/2011-01-31" schemaLocation="http://xbrl.sec.gov/naics/2011/naics-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/sic/2011-01-31" schemaLocation="http://xbrl.sec.gov/sic/2011/sic-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/stpr/2011-01-31" schemaLocation="http://xbrl.sec.gov/stpr/2011/stpr-2011-01-31.xsd" />
  <xsd:annotation>
    <xsd:appinfo>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ns-20140331_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ns-20140331_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ns-20140331_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="ns-20140331_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="CommitmentsAndContingencies" roleURI="http://www.nustarenergy.com/role/CommitmentsAndContingencies">
        <link:definition>2109100 - 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="CommitmentsAndContingenciesNarrative1Details" roleURI="http://www.nustarenergy.com/role/CommitmentsAndContingenciesNarrative1Details">
        <link:definition>2409401 - Disclosure - COMMITMENTS AND CONTINGENCIES 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="CondensedConsolidatedStatementsOfComprehensiveIncome" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatedStatementsOfComprehensiveIncome">
        <link:definition>1002000 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF COMPREHENSIVE INCOME</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CondensedConsolidatingFinancialStatements" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatingFinancialStatements">
        <link:definition>2120100 - 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="CondensedConsolidatingFinancialStatementsTable1Details" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatingFinancialStatementsTable1Details">
        <link:definition>2420402 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS 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="CondensedConsolidatingFinancialStatementsTable2Details" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatingFinancialStatementsTable2Details">
        <link:definition>2420403 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS 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="CondensedConsolidatingFinancialStatementsTable3Details" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatingFinancialStatementsTable3Details">
        <link:definition>2420404 - Disclosure - CONDENSED CONSOLIDATING FINANCIAL STATEMENTS Table 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="CondensedConsolidatingFinancialStatementsTables" roleURI="http://www.nustarenergy.com/role/CondensedConsolidatingFinancialStatementsTables">
        <link:definition>2320301 - 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="ConsolidatedBalanceSheets" roleURI="http://www.nustarenergy.com/role/ConsolidatedBalanceSheets">
        <link:definition>1001000 - 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>1001001 - 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="ConsolidatedStatementsOfCashFlows" roleURI="http://www.nustarenergy.com/role/ConsolidatedStatementsOfCashFlows">
        <link:definition>1003000 - 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="Debt" roleURI="http://www.nustarenergy.com/role/Debt">
        <link:definition>2108100 - 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="DebtNarrativeDetails" roleURI="http://www.nustarenergy.com/role/DebtNarrativeDetails">
        <link:definition>2408402 - Disclosure - DEBT 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="DebtTables" roleURI="http://www.nustarenergy.com/role/DebtTables">
        <link:definition>2308301 - 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="DeiDocument" roleURI="http://www.nustarenergy.com/role/DeiDocument">
        <link:definition>0001000 - 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="DerivativesAndRiskManagementActivities" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivities">
        <link:definition>2111100 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES</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="DerivativesAndRiskManagementActivitiesNarrativeDetails" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivitiesNarrativeDetails">
        <link:definition>2411402 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES 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="DerivativesAndRiskManagementActivitiesTable1Details" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivitiesTable1Details">
        <link:definition>2411403 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES 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="DerivativesAndRiskManagementActivitiesTable2Details" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivitiesTable2Details">
        <link:definition>2411404 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES 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="DerivativesAndRiskManagementActivitiesTable3Details" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivitiesTable3Details">
        <link:definition>2411405 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES Table 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="DerivativesAndRiskManagementActivitiesTables" roleURI="http://www.nustarenergy.com/role/DerivativesAndRiskManagementActivitiesTables">
        <link:definition>2311301 - Disclosure - DERIVATIVES AND RISK MANAGEMENT ACTIVITIES (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="DispositionsAndDiscontinuedOperations" roleURI="http://www.nustarenergy.com/role/DispositionsAndDiscontinuedOperations">
        <link:definition>2103100 - Disclosure - DISPOSITIONS 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="DispositionsAndDiscontinuedOperationsNarrative1Details" roleURI="http://www.nustarenergy.com/role/DispositionsAndDiscontinuedOperationsNarrative1Details">
        <link:definition>2403402 - Disclosure - DISPOSITIONS AND DISCONTINUED OPERATIONS 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="DispositionsAndDiscontinuedOperationsTable1Details" roleURI="http://www.nustarenergy.com/role/DispositionsAndDiscontinuedOperationsTable1Details">
        <link:definition>2403403 - Disclosure - DISPOSITIONS 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="DispositionsAndDiscontinuedOperationsTables" roleURI="http://www.nustarenergy.com/role/DispositionsAndDiscontinuedOperationsTables">
        <link:definition>2303301 - Disclosure - DISPOSITIONS 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="FairValueMeasurements" roleURI="http://www.nustarenergy.com/role/FairValueMeasurements">
        <link:definition>2110100 - Disclosure - 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="FairValueMeasurementsNarrativeDetails" roleURI="http://www.nustarenergy.com/role/FairValueMeasurementsNarrativeDetails">
        <link:definition>2410405 - Disclosure - FAIR VALUE MEASUREMENTS 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="FairValueMeasurementsTable1Details" roleURI="http://www.nustarenergy.com/role/FairValueMeasurementsTable1Details">
        <link:definition>2410402 - Disclosure - FAIR VALUE MEASUREMENTS 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="FairValueMeasurementsTable2Details" roleURI="http://www.nustarenergy.com/role/FairValueMeasurementsTable2Details">
        <link:definition>2410403 - Disclosure - FAIR VALUE MEASUREMENTS 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="FairValueMeasurementsTable3Details" roleURI="http://www.nustarenergy.com/role/FairValueMeasurementsTable3Details">
        <link:definition>2410404 - Disclosure - FAIR VALUE MEASUREMENTS Table 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="FairValueMeasurementsTables" roleURI="http://www.nustarenergy.com/role/FairValueMeasurementsTables">
        <link:definition>2310301 - Disclosure - 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="Inventories" roleURI="http://www.nustarenergy.com/role/Inventories">
        <link:definition>2106100 - Disclosure - INVENTORIES</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="InventoriesTableDetails" roleURI="http://www.nustarenergy.com/role/InventoriesTableDetails">
        <link:definition>2406402 - Disclosure - INVENTORIES 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="InventoriesTables" roleURI="http://www.nustarenergy.com/role/InventoriesTables">
        <link:definition>2306301 - Disclosure - INVENTORIES (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="NetIncomePerUnit" roleURI="http://www.nustarenergy.com/role/NetIncomePerUnit">
        <link:definition>2116100 - Disclosure - NET INCOME PER 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="NetIncomePerUnitParentheticalsDetails" roleURI="http://www.nustarenergy.com/role/NetIncomePerUnitParentheticalsDetails">
        <link:definition>2416403 - Disclosure - NET INCOME PER UNIT Parentheticals (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="NetIncomePerUnitTableDetails" roleURI="http://www.nustarenergy.com/role/NetIncomePerUnitTableDetails">
        <link:definition>2416402 - Disclosure - NET INCOME PER UNIT 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="NetIncomePerUnitTables" roleURI="http://www.nustarenergy.com/role/NetIncomePerUnitTables">
        <link:definition>2316301 - Disclosure - NET INCOME PER 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="OrganizationAndBasisOfPresentation" roleURI="http://www.nustarenergy.com/role/OrganizationAndBasisOfPresentation">
        <link:definition>2101100 - 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="OrganizationAndBasisOfPresentationNarrativeDetails" roleURI="http://www.nustarenergy.com/role/OrganizationAndBasisOfPresentationNarrativeDetails">
        <link:definition>2401402 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION 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="OrganizationAndBasisOfPresentationTables" roleURI="http://www.nustarenergy.com/role/OrganizationAndBasisOfPresentationTables">
        <link:definition>2301301 - Disclosure - ORGANIZATION AND BASIS OF PRESENTATION (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="PartnersEquity" roleURI="http://www.nustarenergy.com/role/PartnersEquity">
        <link:definition>2115100 - 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="PartnersEquityTable1Details" roleURI="http://www.nustarenergy.com/role/PartnersEquityTable1Details">
        <link:definition>2415402 - Disclosure - PARTNERS' EQUITY 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="PartnersEquityTable2Details" roleURI="http://www.nustarenergy.com/role/PartnersEquityTable2Details">
        <link:definition>2415403 - Disclosure - PARTNERS' EQUITY 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="PartnersEquityTable3Details" roleURI="http://www.nustarenergy.com/role/PartnersEquityTable3Details">
        <link:definition>2415404 - Disclosure - PARTNERS' EQUITY Table 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="PartnersEquityTable4Details" roleURI="http://www.nustarenergy.com/role/PartnersEquityTable4Details">
        <link:definition>2415405 - Disclosure - PARTNERS' EQUITY Table 4 (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="PartnersEquityTable5Details" roleURI="http://www.nustarenergy.com/role/PartnersEquityTable5Details">
        <link:definition>2415406 - Disclosure - PARTNERS' EQUITY Table 5 (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="PartnersEquityTables" roleURI="http://www.nustarenergy.com/role/PartnersEquityTables">
        <link:definition>2315301 - 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="RelatedPartyTransactions" roleURI="http://www.nustarenergy.com/role/RelatedPartyTransactions">
        <link:definition>2114100 - Disclosure - RELATED PARTY TRANSACTIONS</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="RelatedPartyTransactionsNarrativeDetails" roleURI="http://www.nustarenergy.com/role/RelatedPartyTransactionsNarrativeDetails">
        <link:definition>2414403 - Disclosure - RELATED PARTY TRANSACTIONS 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="RelatedPartyTransactionsTableDetails" roleURI="http://www.nustarenergy.com/role/RelatedPartyTransactionsTableDetails">
        <link:definition>2414402 - Disclosure - RELATED PARTY TRANSACTIONS 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="RelatedPartyTransactionsTables" roleURI="http://www.nustarenergy.com/role/RelatedPartyTransactionsTables">
        <link:definition>2314301 - Disclosure - RELATED PARTY TRANSACTIONS (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="SegmentInformation" roleURI="http://www.nustarenergy.com/role/SegmentInformation">
        <link:definition>2119100 - 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="SegmentInformationTable1Details" roleURI="http://www.nustarenergy.com/role/SegmentInformationTable1Details">
        <link:definition>2419402 - Disclosure - SEGMENT INFORMATION 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="SegmentInformationTable2Details" roleURI="http://www.nustarenergy.com/role/SegmentInformationTable2Details">
        <link:definition>2419403 - Disclosure - SEGMENT INFORMATION 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="SegmentInformationTables" roleURI="http://www.nustarenergy.com/role/SegmentInformationTables">
        <link:definition>2319301 - 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="StatementsOfCashFlows" roleURI="http://www.nustarenergy.com/role/StatementsOfCashFlows">
        <link:definition>2118100 - Disclosure - 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="StatementsOfCashFlowsTable1Details" roleURI="http://www.nustarenergy.com/role/StatementsOfCashFlowsTable1Details">
        <link:definition>2418402 - Disclosure - STATEMENTS OF CASH FLOWS 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="StatementsOfCashFlowsTable2Details" roleURI="http://www.nustarenergy.com/role/StatementsOfCashFlowsTable2Details">
        <link:definition>2418403 - Disclosure - STATEMENTS OF CASH FLOWS 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="StatementsOfCashFlowsTables" roleURI="http://www.nustarenergy.com/role/StatementsOfCashFlowsTables">
        <link:definition>2318301 - Disclosure - STATEMENTS OF CASH FLOWS (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xsd:appinfo>
  </xsd:annotation>
  <xsd:element id="ns_AdministrativeAgreementMaturityDate" name="AdministrativeAgreementMaturityDate" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_AdministrativeFeesReductionDescription" name="AdministrativeFeesReductionDescription" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_AsphaltAndFuelsMarketingSegmentMember" name="AsphaltAndFuelsMarketingSegmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_AsphaltJvMember" name="AsphaltJvMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_BondProceedsHeldInTrust" name="BondProceedsHeldInTrust" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_CondensedConsolidatingFinancialStatementsAbstract" name="CondensedConsolidatingFinancialStatementsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_CondensedConsolidatingStatementsofComprehensiveIncomeTableTextBlock" name="CondensedConsolidatingStatementsofComprehensiveIncomeTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ContingentconsiderationMember" name="ContingentconsiderationMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_ContributionsFromDistributionsToAffiliates" name="ContributionsFromDistributionsToAffiliates" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_Cumulativeequitymethodlossesinexcessofinvestment" name="Cumulativeequitymethodlossesinexcessofinvestment" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_DebtCoverageRatio" name="DebtCoverageRatio" nillable="true" substitutionGroup="xbrli:item" type="xbrli:decimalItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_DepreciationDepletionAndAmortizationFromContinuingAndDiscontinuedOperations" name="DepreciationDepletionAndAmortizationFromContinuingAndDiscontinuedOperations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_DistributionDateOfRecord" name="DistributionDateOfRecord" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_DistributionMadeToMemberOrLimitedPartnerAnouncementDate" name="DistributionMadeToMemberOrLimitedPartnerAnouncementDate" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_DistributionPaymentDate" name="DistributionPaymentDate" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_DistributionPerLimitedPartnershipUnitOutstanding" name="DistributionPerLimitedPartnershipUnitOutstanding" nillable="true" substitutionGroup="xbrli:item" type="num:perShareItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_DistributionsMadeToLimitedAndGeneralPartnersByDistributionTableTextBlock" name="DistributionsMadeToLimitedAndGeneralPartnersByDistributionTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_DistributionsMadeToLimitedPartnersAndGeneralPartnerLineItems" name="DistributionsMadeToLimitedPartnersAndGeneralPartnerLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_DocumentInformationAbstract" name="DocumentInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_EpuDistributionsLessThanGreaterThanEarnings" name="EpuDistributionsLessThanGreaterThanEarnings" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ns_EpuDistributionsLessThanGreaterThanEarningsAllocatedToGeneralPartner" name="EpuDistributionsLessThanGreaterThanEarningsAllocatedToGeneralPartner" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_EpuDistributionsLessThanGreaterThanEarningsAllocatedToLimitedPartners" name="EpuDistributionsLessThanGreaterThanEarningsAllocatedToLimitedPartners" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_EpuGeneralPartnerAllocation" name="EpuGeneralPartnerAllocation" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_EpuLimitedPartnersAllocation" name="EpuLimitedPartnersAllocation" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_EquityMethodInvestmentPercentVotingInterestSold" name="EquityMethodInvestmentPercentVotingInterestSold" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_FairValueAndCarryingValueOfDebtAndNoteReceivableFromRelatedPartyTableTextBlock" name="FairValueAndCarryingValueOfDebtAndNoteReceivableFromRelatedPartyTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasis" name="FairValueAssetsAndLiabilitiesMeasuredOnRecurringBasis" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_GeneralPartnerAllocationOfNetIncomeExcludingIncentiveDistribution" name="GeneralPartnerAllocationOfNetIncomeExcludingIncentiveDistribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ns_GeneralPartnerDistributionsIncludingIncentiveDistributions" name="GeneralPartnerDistributionsIncludingIncentiveDistributions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_GeneralPartnerEarningsAbstract" name="GeneralPartnerEarningsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_GeneralPartnerIncentiveDistribution" name="GeneralPartnerIncentiveDistribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_GeneralPartnerInterestDistribution" name="GeneralPartnerInterestDistribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_GeneralPartnerOwnershipInterest" name="GeneralPartnerOwnershipInterest" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_GozoneBondsMember" name="GozoneBondsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_IncomeLossFromSubsidiaries" name="IncomeLossFromSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ns_IntercompanyPayable" name="IntercompanyPayable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ns_IntercompanyReceivable" name="IntercompanyReceivable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_InterestExpenseNetIncludingRelatedParty" name="InterestExpenseNetIncludingRelatedParty" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_IntersegmentrevenueMember" name="IntersegmentrevenueMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_InventoryCrudeOil" name="InventoryCrudeOil" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_InvestmentInSubsidiaries" name="InvestmentInSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ns_InvestmentInWhollyOwnedSubsidiaries" name="InvestmentInWhollyOwnedSubsidiaries" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_LimitedPartnerDistribution" name="LimitedPartnerDistribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_LimitedPartnerEarningsAbstract" name="LimitedPartnerEarningsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_LimitedPartnershipGeneralPartnerOwnershipInterest" name="LimitedPartnershipGeneralPartnerOwnershipInterest" nillable="true" substitutionGroup="xbrli:item" type="xbrli:decimalItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_Logisitics2012RevolvingCreditAgreementMember" name="Logisitics2012RevolvingCreditAgreementMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_MaturityDateofTermLoanReceivable" name="MaturityDateofTermLoanReceivable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:dateItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_MaximumAmountAvailableCreditFacilityToRelatedParty" name="MaximumAmountAvailableCreditFacilityToRelatedParty" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ns_MaximumAmountGuarantees" name="MaximumAmountGuarantees" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_NetIncomeAllocationLineItems" name="NetIncomeAllocationLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_NetIncomeAllocationTable" name="NetIncomeAllocationTable" nillable="true" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_NetIncomeLessGeneralPartnerIncentiveDistribution" name="NetIncomeLessGeneralPartnerIncentiveDistribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="ns_NetIntercompanyBorrowingsRepayments" name="NetIntercompanyBorrowingsRepayments" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_NumberOfGuaranteesWithUnlimitedExposure" name="NumberOfGuaranteesWithUnlimitedExposure" nillable="true" substitutionGroup="xbrli:item" type="xbrli:integerItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_NustarEnergyLpMember" name="NustarEnergyLpMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_NustarGpLlcAndAsphaltJvMember" name="NustarGpLlcAndAsphaltJvMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_NustarGpLlcMember" name="NustarGpLlcMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_NustarLogisticsLpMember" name="NustarLogisticsLpMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_NustarPipelineOperatingPartnershipLpMember" name="NustarPipelineOperatingPartnershipLpMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_OtherAccruedTaxesCurrent" name="OtherAccruedTaxesCurrent" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ns_OwnershipPercentageOfAcquiringEntity" name="OwnershipPercentageOfAcquiringEntity" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_PartnersEquityActivityLineItems" name="PartnersEquityActivityLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_Payables" name="Payables" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="ns_PercentageofServicesUsedUnderAdministrativeServicesAgreement" name="PercentageofServicesUsedUnderAdministrativeServicesAgreement" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_ProceedsPaymentFromTerminationOfInterestRateSwaps" name="ProceedsPaymentFromTerminationOfInterestRateSwaps" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_ProductImbalancesAssetLiabilities" name="ProductImbalancesAssetLiabilities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_ReductioninCreditSupport" name="ReductioninCreditSupport" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_RelatedPartyGeneralAndAdministrativeExpense" name="RelatedPartyGeneralAndAdministrativeExpense" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_RelatedPartyOperatingExpenses" name="RelatedPartyOperatingExpenses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="ns_RelatedPartyRevenueExpensesInDiscontinuedOperations" name="RelatedPartyRevenueExpensesInDiscontinuedOperations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_RelatedPartyRevenueMember" name="RelatedPartyRevenueMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_Relatedpartyrevenueindiscontinuedoperations" name="Relatedpartyrevenueindiscontinuedoperations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_SanAntonioRefinerySaleMember" name="SanAntonioRefinerySaleMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_ScheduleOfCalculationOfNetIncomeApplicableToGeneralPartnerTableTextBlock" name="ScheduleOfCalculationOfNetIncomeApplicableToGeneralPartnerTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_ScheduleOfDistributionsToGeneralAndLimitedPartnersTableTextBlock" name="ScheduleOfDistributionsToGeneralAndLimitedPartnersTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ScheduleOfDistributionsToLimitedAndGeneralPartnersTable" name="ScheduleOfDistributionsToLimitedAndGeneralPartnersTable" nillable="true" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ScheduleOfNetIncomePerUnitLineItems" name="ScheduleOfNetIncomePerUnitLineItems" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ScheduleOfPartnersEquityActivityTable" name="ScheduleOfPartnersEquityActivityTable" nillable="true" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ServicesAgreementMember" name="ServicesAgreementMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ServicesAgreementsBetweenGeneralPartnerandOtherPartiesAxis" name="ServicesAgreementsBetweenGeneralPartnerandOtherPartiesAxis" nillable="true" substitutionGroup="xbrldt:dimensionItem" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ServicesAgreementsBetweenGeneralPartnerandOtherPartiesDomain" name="ServicesAgreementsBetweenGeneralPartnerandOtherPartiesDomain" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_StorageSegmentMember" name="StorageSegmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_TermLoanReceivable" name="TermLoanReceivable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="ns_TermLoanReceivableFaceAmountStepDown1" name="TermLoanReceivableFaceAmountStepDown1" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="instant" />
  <xsd:element id="ns_TermLoanReceivableFaceAmountStepDown2" name="TermLoanReceivableFaceAmountStepDown2" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="ns_TerminalsHeldforSaleMember" name="TerminalsHeldforSaleMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_TexstarAssetAcquisitionMember" name="TexstarAssetAcquisitionMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_ThirdPartyRevenueMember" name="ThirdPartyRevenueMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="ns_TotalCashDistributions" name="TotalCashDistributions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="ns_TransportationSegmentMember" name="TransportationSegmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
</xsd:schema>
</XBRL>
