Exhibit 5.01

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

July 2, 2019

NuStar Energy L.P.

19003 IH-10 West

San Antonio, Texas 78257

Re:          Registration Statement on Form S-3

Ladies and Gentlemen:

We refer to the Registration Statement on Form S-3 (the “Registration Statement”) being filed by NuStar Energy L.P., a Delaware limited partnership (the “Partnership”), NuStar Logistics, L.P., a Delaware limited partnership (“NuStar Logistics”), and NuStar Pipeline Operating Partnership L.P., a Delaware limited partnership (“NuPOP”), with the Securities and Exchange Commission (the “SEC”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the registration of an unlimited amount of:

(i)          common units representing limited partner interests in the Partnership (“Common Units”);

(ii)          preferred units representing limited partner interests in the Partnership (“Preferred Units”);

(iii)          debt securities of NuStar Logistics (the “Debt Securities”), which may be unsecured senior debt securities (the “Senior Debt Securities”) and/or unsecured subordinated debt securities (the “Subordinated Debt Securities”); and

(iv)          guarantees of the Partnership and NuPOP with respect to the Debt Securities (the “Guarantees”).

The Common Units, the Preferred Units, the Debt Securities and the Guarantees are collectively referred to herein as the “Securities.”

Unless otherwise specified in the applicable prospectus supplement, the Senior Debt Securities will be issued under the indenture, dated as of July 15, 2002 (as amended by the Third Supplemental Indenture thereto, dated as of July 1, 2005, the “Senior Indenture”) among NuStar Logistics, the Partnership, NuPop and Wells Fargo Bank, National Association (as successor trustee, the “Trustee”) and the Subordinated Debt Securities will be issued under the indenture, dated as of January 22, 2013 (the “Subordinated Indenture” and, together with the Senior Indenture, the “Indentures”), among NuStar Logistics, the Partnership, NuPOP and the Trustee.

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

NuStar Energy L.P.

July 2, 2019

Page 2

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: (i) the Registration Statement and the exhibits thereto; (ii) the certificate of limited partnership of the Partnership, as amended to the date hereof (the “Certificate of Limited Partnership”); (iii) the Eighth Amended and Restated Agreement of Limited Partnership of the Partnership (together with the Certificate of Limited Partnership, the “Partnership Organizational Documents”); (iv) the Certificate of Limited Partnership of Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “General Partner”), as amended to the date hereof; (v) the First Amended and Restated Limited Partnership Agreement of the General Partner, as amended to the date hereof; (vi) the Certificate of Formation of NuStar GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“NuStar GP”), as amended to the date hereof; (vii) the Second Amended and Restated Limited Liability Company Agreement of NuStar GP; (viii) the Certificate of Limited Partnership of NuStar Logistics, as amended to the date hereof (the “NuStar Logistics Certificate of Limited Partnership”); (ix) the Second Amended and Restated Agreement of Limited Partnership of NuStar Logistics, as amended to the date hereof (together with the NuStar Logistics Certificate of Limited Partnership, the “NuStar Logistics Organizational Documents”); (x) the Certificate of Incorporation of NuStar GP, Inc., a Delaware corporation and the general partner of NuStar Logistics (“GP Inc.”), as amended to the date hereof; (xi) the Bylaws of GP Inc.; (xii) the Certificate of Limited Partnership of NuPOP, as amended to the date hereof (the “NuPOP Certificate of Limited Partnership”); (xiii) the Amended and Restated Agreement of Limited Partnership of NuPOP, as amended to the date hereof (together with the NuPOP Certificate of Limited Partnership, the “NuPOP Organizational Documents”); (xiv) the Certificate of Formation of NuStar Pipeline Company, LLC, a Delaware limited liability company and the general partner of NuPOP (“NuStar Pipeline” and, together with the Partnership, NuStar Logistics, NuPOP, the General Partner, NuStar GP and GP Inc., the “NuStar Entities”), as amended to the date hereof; (xv) the Limited Liability Company Agreement of NuStar Pipeline, as amended to the date hereof; and (xvi) the resolutions (the “Resolutions”) adopted by each of the board of directors of NuStar GP (the “Partnership Board”) and the board of directors of GP Inc. (the “NuStar Logistics Board”) relating to the Registration Statement. We have also examined originals, or copies of originals certified to our satisfaction, of such agreements, documents, certificates and statements of the NuStar Entities and others, 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 NuStar Entities.

NuStar Energy L.P.

July 2, 2019

Page 3

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

1.          With respect to an offering of Common Units covered by the Registration Statement, such Common Units will be duly authorized, validly issued and purchasers of such Common Units will have no obligation, solely by reason of their ownership of such Common Units, to make any contributions to the Partnership or any further payments for their purchase of such Common Units and will have no personal liability, solely by reason of their ownership of such Common Units, to creditors of the Partnership for any of its debts, liabilities or other obligations when: (i) the Registration Statement, as finally amended (including any necessary post-effective amendments), shall have become effective under the Securities Act; (ii) a prospectus supplement with respect to the sale of such Common Units shall have been filed with the SEC in compliance with the Securities Act and the rules and regulations thereunder; (iii) the Partnership Board or a duly authorized committee thereof shall have duly adopted final resolutions in conformity with the Partnership Organizational Documents and the Resolutions authorizing the issuance and sale of such Common Units; and (iv) certificates representing such Common Units shall have been duly executed, countersigned and registered and duly delivered in accordance with the applicable definitive purchase, underwriting or similar agreement upon payment of the agreed consideration therefor or, if any such Common Units are to be issued in uncertificated form, the Partnership’s books shall reflect the issuance of such Common Units in accordance with the applicable definitive purchase, underwriting or similar agreement upon payment of the agreed consideration therefor.

2.          With respect to an offering of Preferred Units covered by the Registration Statement, such Preferred Units will be duly authorized, validly issued and 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 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 when: (i) the Registration Statement, as finally amended (including any necessary post-effective amendments), shall have become effective under the Securities Act; (ii) a prospectus supplement with respect to the sale of such Preferred Units shall have been filed with the SEC in compliance with the Securities Act and the rules and regulations thereunder; (iii) the Partnership Board or a duly authorized committee thereof shall have duly adopted final resolutions in conformity with the Partnership Organizational Documents establishing the designations, preferences, rights, qualifications, limitations or restrictions of such Preferred Units and the Resolutions authorizing the issuance and sale of such Preferred Units; and (iv) certificates representing such Preferred Units shall have been duly executed, countersigned and registered and duly delivered in accordance with the applicable definitive purchase, underwriting or similar agreement upon payment of the agreed consideration therefor or, if any such Preferred Units are to be issued in uncertificated form, the Partnership’s books shall reflect the issuance of such Preferred Units in accordance with the applicable definitive purchase, underwriting or similar agreement upon payment of the agreed consideration therefor.

NuStar Energy L.P.

July 2, 2019

Page 4

3.          The Debt Securities of each series covered by the Registration Statement will constitute valid and binding obligations of NuStar Logistics when: (i) the Registration Statement, as finally amended (including any necessary post-effective amendments), shall have become effective under the Securities Act; (ii) a prospectus supplement with respect to such series of Debt Securities shall have been filed with the SEC in compliance with the Securities Act and the rules and regulations thereunder; (iii) all necessary limited partnership action shall have been taken by NuStar Logistics to authorize the form, terms, execution, delivery, performance, issuance and sale of such series of Debt Securities as contemplated by the Registration Statement, the prospectus supplement relating to such Debt Securities and the applicable Indenture and to authorize the execution, delivery and performance of a supplemental indenture or officers’ certificate establishing the form and terms of such series of Debt Securities as contemplated by such Indenture; (iv) a supplemental indenture or officers’ certificate establishing the form and terms of such series of Debt Securities shall have been duly executed and delivered by NuStar Logistics and the Trustee (in the case of such a supplemental indenture) or by duly authorized officers of GP Inc. (in the case of such an officers’ certificate), in each case in accordance with the provisions of the NuStar Logistics Organizational Documents, final resolutions of the NuStar Logistics Board or a duly authorized committee thereof and the applicable Indenture; and (v) the certificates evidencing the Debt Securities of such series shall have been duly executed and delivered by GP Inc., authenticated by the Trustee and issued, all in accordance with the NuStar Logistics Organizational Documents, final resolutions of the NuStar Logistics Board or a duly authorized committee thereof, the applicable Indenture and the supplemental indenture or officers’ certificate, as the case may be, establishing the form and terms of the Debt Securities of such series, and shall have been duly delivered in accordance with the applicable definitive purchase, underwriting or similar agreement to the purchasers thereof against payment of the agreed consideration therefor.

4.          The Guarantees will constitute a validly issued and binding obligation of the Partnership and/or NuPOP when: (i) the Registration Statement, as finally amended (including any necessary post-effective amendments), shall have become effective under the Securities Act; (ii) a prospectus supplement with respect to the Guarantees shall have been filed with the SEC in compliance with the Securities Act and the rules and regulations thereunder; (iii) the Partnership Board or a duly authorized committee thereof shall have duly adopted final resolutions in conformity with the Partnership Organizational Documents, the NuPOP Organizational Documents and the Resolutions authorizing the issuance of the Guarantees and (iv) the Debt Securities to which the Guarantees relate have been duly issued as set forth in paragraph 3 above.

Our opinions are subject to bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance, fraudulent transfer and other similar laws relating to or affecting creditors’ rights generally and to general equitable principles (regardless of whether considered in a proceeding in equity or at law), including concepts of commercial reasonableness, good faith and fair dealing and the possible unavailability of specific performance or injunctive relief. Our opinion is also subject to (i) provisions of law which may require that a judgment for money damages rendered by a court in the United States of America be expressed only in United States dollars, (ii) requirements that a claim with respect to any Debt Securities or other obligations that are denominated or payable other than in United States dollars (or a judgment denominated or payable other than in United States dollars in respect of such claim) be converted into United States dollars at a rate of exchange prevailing on a date determined pursuant to applicable law and (iii) governmental authority to limit, delay or prohibit the making of payments outside of the United States of America or in a foreign currency.

NuStar Energy L.P.

July 2, 2019

Page 5

For the purposes of this letter, we have assumed that, at the time of the issuance, sale and delivery of any of the Securities:

(a)          the Securities being offered will be issued and sold as contemplated in the Registration Statement and the prospectus supplement relating thereto;

(b)          the execution, delivery and performance by NuStar Logistics of such Debt Securities, the applicable Indenture, and the issuance sale and delivery of the Debt Securities will not (i) contravene or violate the NuStar Logistics Organizational Documents, (ii) violate any law, rule or regulation applicable to NuStar Logistics, (iii) result in a default under or breach of any agreement or instrument binding upon NuStar Logistics or any order, judgment or decree of any court or governmental authority applicable to NuStar Logistics or (iv) require any authorization, approval or other action by, or notice to or filing with, any court or governmental authority (other than such authorizations, approvals, actions, notices or filings which shall have been obtained or made, as the case may be, and which shall be in full force and effect);

(c)          the authorization thereof by the applicable NuStar Entity, as the case may be, will not have been modified or rescinded, and there will not have occurred any change in law affecting the validity, legally binding character or enforceability thereof; and

(d)          the Partnership Organizational Documents, the NuStar Logistics Organizational Documents and the NuPOP Organizational Documents, each as currently in effect, will not have been modified or amended and will be in full force and effect.

We have further assumed that the Senior Indenture, each indenture supplement to the Senior Indenture, the Subordinated Indenture and each supplement to the Subordinated Indenture, will be governed by the laws of the State of New York.

With respect to each instrument or agreement referred to in or otherwise relevant to the opinions set forth herein (each, an “Instrument”), we have assumed, to the extent relevant to the opinions set forth herein, that (i) each party to such Instrument (if not a natural person) was duly organized or formed, as the case may be, and was at all relevant times and is validly existing and in good standing under the laws of its jurisdiction of organization or formation, as the case may be, and had at all relevant times and has full right, power and authority to execute, deliver and perform its obligations under such Instrument; (ii) such Instrument has been duly authorized, executed and delivered by each party thereto; and (iii) such Instrument was at all relevant times and is a valid, binding and enforceable agreement or obligation, as the case may be, of, each party thereto.

NuStar Energy L.P.

July 2, 2019

Page 6

We have also assumed that no event has occurred or will occur that would cause the release of the Guarantees by the Partnership or NuPOP under the terms of the applicable Indenture.

This opinion letter is limited to the Delaware Revised Uniform Limited Partnership Act, the Delaware Limited Liability Company Act, the General Corporation Law of the State of Delaware and the laws of the State of New York (excluding the securities laws of the State of New York). 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.

Very truly yours,

/s/ Sidley Austin LLP