600 Travis, Suite 4200
Houston, Texas 77002 713.220.4200 Phone 713.220.4285 Fax andrewskurth.com   EXHIBIT 8.01

June 30, 2016

NuStar Energy L.P.

19003 IH-10 West

San Antonio, Texas 78257

Ladies and Gentlemen:

We have acted as special counsel to NuStar Energy L.P., a Delaware limited partnership (the “Partnership”), NuStar Logistics, L.P., a Delaware limited partnership (“Logistics”) and NuStar Pipeline Operating Partnership L.P., a Delaware limited partnership (“NuPOP”) in connection with the preparation of a registration statement on Form S-3 (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Act”), on June 30, 2016. The Registration Statement relates to the offering, from time to time, as set forth in the Registration Statement, the form of prospectus contained therein (the “Prospectus”) and one or more supplements to the Prospectus (each, a “Prospectus Supplement”), of: (i) common units representing limited partner interests in the Partnership (“Common Units”); (ii) preferred units representing limited partner interests in the Partnership (the “Preferred Units”); (iii) debt securities of Logistics, which may be either senior or subordinated in right of payment, and may be issued in one or more series (the “Debt Securities”); and (iv) guarantees of the Partnership or NuPOP, with respect to the Debt Securities (the “Guarantees”); to be issued and sold from time to time pursuant to Rule 415 of the Act. In connection therewith, we have participated in the preparation of the discussion set forth under the caption “Material Tax Consequences” in the Registration Statement (the “Discussion”).

The Discussion, subject to the qualifications and assumptions stated in the Discussion and the limitations and qualifications set forth herein, constitutes our opinion as to the material United States federal income tax consequences for purchasers of the Common Units pursuant to the Offering.

This opinion letter is limited to the matters set forth herein, and no opinions are intended to be implied or may be inferred beyond those expressly stated herein. Our opinion is rendered as of the date hereof and we assume no obligation to update or supplement this opinion or any matter related to this opinion to reflect any change of fact, circumstances, or law after the date hereof. In addition, our opinion is based on the assumption that the matter will be properly presented to the applicable court.

Furthermore, our opinion is not binding on the Internal Revenue Service or a court. In addition, we must note that our opinion represents merely our best legal judgment on the matters presented and that others may disagree with our conclusion. There can be no assurance that the Internal Revenue Service will not take a contrary position or that a court would agree with our opinion if litigated.

Austin    Beijing    Dallas    Dubai    Houston     London    New York    Research Triangle Park    The Woodlands    Washington, DC

NuStar Energy L.P.

June 30, 2016

Page 2

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the references to our firm and this opinion contained in the Discussion. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission relating thereto, with respect to any part of the Registration Statement, including this exhibit to the Registration Statement.

Very truly yours,

/s/ Andrews Kurth LLP