EXHIBIT 5.1

  SIDLEY AUSTIN LLP 1000 LOUISIANA STREET SUITE 6000 HOUSTON, TX 77002 +1 713 495 4500 +1 713 495 7799 FAX   AMERICA • ASIA PACIFIC • EUROPE

[●], 2018

NuStar Energy L.P.

19003 IH-10 West

San Antonio, Texas 78257

Re: Registration Statement on Form S-4

Ladies and Gentlemen:

We refer to the Registration Statement on Form S-4 (the “Registration Statement”) being 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”), relating to the registration of common units representing limited partner interests in the Partnership (the “Common Units”). The Common Units are to be issued pursuant to the terms of the Agreement and Plan of Merger, dated as of February 7, 2018 (the “Merger Agreement”), by and among 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”), Marshall Merger Sub LLC, a Delaware limited liability company and a wholly owned subsidiary of the Partnership (“Merger Sub”), NuStar GP Holdings, LLC, a Delaware limited liability company (“NSH”), and Riverwalk Holdings, LLC, a Delaware limited liability company and a wholly owned subsidiary of NSH, which provides, among other things, that Merger Sub will merge with and into NSH, with NSH surviving the merger and becoming a wholly owned subsidiary of the Partnership (the “Merger”). The Merger is subject to satisfaction or waiver of a number of conditions.

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

We have examined the: (i) Registration Statement; (ii) the Merger Agreement; (iii) the Certificate of Limited Partnership of the Partnership, as amended to date; (iv) the Sixth Amended and Restated Agreement of Limited Partnership of the Partnership, dated November 30, 2017, as amended to date; (v) the form of the Seventh Amended and Restated Agreement of Limited Partnership of the Partnership (the “Seventh Partnership Agreement”), which will become effective as of the Effective Time (as defined in the Merger Agreement); (vi) the Certificate of Limited Partnership of the General Partner, as amended to date; (vii) the First Amended and Restated Limited Partnership Agreement of the General Partner, dated April 16, 2001, as amended to date; (viii) the Certificate of Formation of NuStar GP, as amended to date;

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

NuStar Energy L.P.

[●], 2018

Page 2

(ix) the First Amended and Restated Limited Liability Company Agreement of NuStar GP, dated June 5, 2000, as amended to date; (x) the form of the Second Amended and Restated Limited Liability Company Agreement of NuStar GP (the “NuStar GP LLC Agreement”), which will become effective as of the Effective Time; and (xi) the resolutions adopted by the Board of Directors of NuStar GP relating to the Registration Statement, the Merger Agreement and the issuance of the Common Units by the Partnership. 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, the conformity with the original documents of any copies thereof submitted to us for examination and that each of the Seventh Partnership Agreement and the NuStar GP LLC Agreement, when they become effective at the Effective Time, will be substantially identical to the forms of each such agreement provided 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 NuStar GP.

Based on the foregoing, we are of the opinion that when (i) the Registration Statement, as finally amended, shall have become effective under the Securities Act, (ii) the Merger shall have become effective under the Delaware Limited Liability Company Act (the “DLLCA”) and (iii) a certificate representing each Common Unit shall have been duly executed, countersigned, registered and delivered to the person entitled thereto or, if the Common Unit is to be issued in uncertificated form, the Partnership’s books shall reflect the issuance of such Common Unit to the person entitled thereto, in each case in accordance with the terms of the Merger Agreement, (a) each Common Unit has been duly authorized, (b) each Common Unit will be validly issued and (c) the person entitled to such Common Unit will have no obligation, solely by reason of their ownership of such Common Unit, to make any contributions to the Partnership or any further payments for their purchase of such Common Unit, and such persons will have no personal liability, solely by reason of their ownership of such Common Unit, to creditors of the Partnership for any of its debts, liabilities or other obligations.

This opinion letter is limited to the Delaware Revised Uniform Limited Partnership Act and the DLLCA. 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

NuStar Energy L.P.

[●], 2018

Page 3

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.

Very truly yours,