Exhibit 5.1

				600 Travis, Suite 4200 Houston, Texas 77002 +1.713.220.4200 Phone +1.713.220.4285 Fax andrewskurthkenyon.com

November 25, 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”), in connection with the issuance and sale by the Partnership of up to 9,200,000 8.50% Series A Fixed-to-Floating Rate Cumulative Redeemable Perpetual Preferred Units (including the units to be issued upon exercise of the underwriters’ option to purchase up to 1,200,000 additional units) (the “Preferred Units”) pursuant to a registration statement on Form S-3 (Registration No. 333-212338) filed and immediately effective with the Securities and Exchange Commission (the “SEC”) on June 30, 2016 (the “Registration Statement”). A prospectus supplement dated November 17, 2016, which, together with the prospectus filed with the Registration Statement (the “Base Prospectus”) constitute the “Prospectus,” was filed with the SEC on November 18, 2016 pursuant to Rule 424(b) promulgated under the Securities Act of 1933, as amended (the “Securities Act”).

In rendering the opinions set forth herein, we have read and examined and relied on originals or copies, certified or otherwise identified to our satisfaction, of such records of the Partnership, of Riverwalk Logistics, L.P., a Delaware limited partner and the general partner of the Partnership (the “General Partner”), and of NuStar GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“NuStar GP”), and such other documents, certificates and records as we have deemed necessary or appropriate as a basis for the opinions set forth herein, including the Underwriting Agreement, dated November 17, 2016 (the “Underwriting Agreement”), by and among the Partnership, the General Partner and NuStar GP on the one hand, and Wells Fargo Securities, LLC, Merrill Lynch, Pierce, Fenner & Smith Incorporated and UBS Securities LLC, as representatives of the several underwriters named in Schedule I to the Underwriting Agreement, on the other hand. In our examination, we have assumed, without independent investigation, (a) the genuineness of the signatures on all documents that we have examined, (b) the legal capacity of all natural persons, (c) the authenticity of all documents supplied to us as originals, (d) the conformity to the authentic originals of all documents supplied to us as certified, photostatic or faxed copies and (e) the authenticity of the originals of such latter documents. We have also assumed that all Preferred Units sold pursuant to the Underwriting Agreement will be issued and sold in the manner described in the Prospectus and in accordance with the terms of the Underwriting Agreement.

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

NuStar Energy L.P.

November 25, 2016

Page 2

Our opinions expressed herein are limited to the Delaware Revised Uniform Limited Partnership Act and the Delaware Limited Liability Company Act, and we express no opinion as to the laws of any other jurisdiction.

Based upon the foregoing and subject to the limitations, qualifications, exceptions and assumptions set forth herein, we are of the opinion that when any of the Preferred Units have been issued and delivered against payment therefor in accordance with the terms of the Underwriting Agreement, (a) such Preferred Units will be validly issued and (b) purchasers of such Preferred Units will have no obligation, solely by reason of their ownership of such Preferred Units, to make any contributions to the Partnership or any further payments for their purchase of such Preferred Units, and such purchasers will have no personal liability, solely by reason of their ownership of such Preferred Units, to creditors of the Partnership for any of its debts, liabilities or other obligations.

We consent to the filing by you of this opinion as an exhibit to the Partnership’s Current Report on Form 8-K filed on the date hereof, and we further consent to the use of our name under the caption “Legal Matters” in the Prospectus. 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 Securities Act, or the rules and regulations of the SEC. This opinion is expressed as of the date hereof, and we disclaim any undertaking to advise you of any subsequent changes in the facts stated or assumed herein or of any subsequent changes in law.