Exhibit 5.1

November 30, 2017

NuStar Energy L.P.

19003 IH-10 West

San Antonio, Texas 78257

Ladies and Gentlemen:

We refer to the Registration Statement on Form S-3, File No. 333-212338 (the “Registration Statement”), filed by NuStar Energy L.P., a Delaware limited partnership (the “Partnership”), with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), which Registration Statement became effective upon filing pursuant to Rule 462(e) under the Securities Act. Pursuant to the Registration Statement, the Partnership is issuing up to 6,900,000 9.00% Series C Fixed-to-Floating Rate Cumulative Redeemable Perpetual Preferred Units (including the units to be issued upon the exercise of the Underwriters’ option to purchase up to 900,000 additional Preferred Units) (the “Preferred Units”). The Preferred Units are to be sold by the Partnership pursuant to an underwriting agreement dated November 27, 2017 (the “Underwriting Agreement”), by and among (a) the Partnership, Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “General Partner”), NuStar GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“NuStar GP”) and (b) Wells Fargo Securities, LLC, Merrill Lynch, Pierce, Fenner & Smith Incorporated, J.P. Morgan Securities LLC and RBC Capital Markets, LLC, as representatives of the several underwriters named in Schedule I to the Underwriting Agreement (collectively, the “Underwriters”).

This opinion letter is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

As the basis for the opinions hereinafter expressed, we have examined and relied on originals or copies, certified or otherwise identified to our satisfaction, of the following: (i) the Certificate of Limited Partnership of the Partnership, as amended to date (the “Certificate of Limited Partnership”); (ii) the Fifth Amended and Restated Agreement of Limited Partnership of the Partnership, dated April 28, 2017; (iii) the Sixth Amended and Restated Agreement of Limited Partnership of the Partnership, dated November 30, 2017 (the “Partnership Agreement”); (iv) the Certificate of Limited Partnership of the General Partner, as amended to date; (v) the First Amended and Restated Limited Partnership Agreement of the General Partner, dated April 16, 2001, as amended to date; (vi) the Certificate of Formation of NuStar GP, as amended to date; (vii) the First Amended and Restated Limited Liability Company Agreement of NuStar GP, dated June 5, 2000, as amended to date; (viii) the resolutions of the Board of

Sidley Austin LLP is a limited liability partnership practicing in affiliation with other Sidley Austin partnerships.

NuStar Energy L.P.

November 30, 2017

Page 2

Directors of NuStar GP and the Pricing Committee of NuStar GP, with respect to the Registration Statement and the issuance of the Preferred Units; (ix) the Registration Statement; and (x) the prospectus supplement dated November 27, 2017. We have also examined originals, or copies of originals certified to our satisfaction, of such agreements, documents, certificates and statements of the Partnership, the General Partner and NuStar GP and other corporate documents and instruments, and have examined such questions of law, as we have considered relevant and necessary as a basis for this opinion letter. We have assumed the authenticity of all documents submitted to us as originals, the genuineness of all signatures, the legal capacity of all persons and the conformity with the original documents of any copies thereof submitted to us for examination. As to facts relevant to the opinions expressed herein, we have relied without independent investigation or verification upon, and assumed the accuracy and completeness of, certificates, letters and oral and written statements and representations of public officials and officers and other representatives of the Company.

Based on and subject to the foregoing and the other limitations, qualifications and assumptions set forth herein, we are of the opinion that:

1.     The issuance and sale of 6,000,000 of the Preferred Units covered by the Registration Statement pursuant to the Underwriting Agreement have been duly authorized by the Partnership, and when such Preferred Units have been paid for, issued and delivered 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.

2.     The issuance and sale of 900,000 of the Preferred Units covered by the Registration Statement in connection with any exercise of the over-allotment option granted by the Partnership to the Underwriters pursuant to the Underwriting Agreement have been duly authorized by the Partnership, and when such Preferred Units have been paid for, issued and delivered 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.

For the purposes of paragraph 2 of this opinion letter, we have assumed that, at the time of the issuance, sale and delivery of Preferred Units pursuant to the over-allotment option: (i) the authorization thereof by NuStar GP will not have been modified or rescinded, and there will not have occurred any change in law affecting the validity thereof; and (ii) the Certificate of Limited Partnership and the Partnership Agreement, as currently in effect, will not have been modified or amended and will be in full force and effect.

NuStar Energy L.P.

November 30, 2017

Page 3

This opinion letter is limited to the Delaware Revised Uniform Limited Partnership Act and the Delaware Limited Liability Company Act. We express no opinion as to the laws, rules or regulations of any other jurisdiction, including, without limitation, the federal laws of the United States of America or any state securities or blue sky laws.

We hereby consent to the filing of this opinion letter as an Exhibit to the Registration Statement and to all references to our Firm included in or made a part of the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act.