Exhibit 5.1

January 17, 2013

Ladies and Gentlemen:

We have acted as special counsel to NuStar Energy L.P., a Delaware limited partnership (the “Partnership”), NuStar Pipeline Operating Partnership L.P., a Delaware limited partnership and wholly owned subsidiary of the Partnership (“NuPOP,” and together with the Partnership, the “Guarantors”), and NuStar Logistics, L.P., a Delaware limited partnership and wholly owned subsidiary of the Partnership (the “Issuer”), in connection with the public offering of $402,500,000 aggregate principal amount of the Issuer’s 7.625% Fixed-to-Floating Rate Subordinated Notes due 2043 (the “Notes”).  The Notes are being issued under an Indenture to be dated as of January 22, 2013 (the “Subordinated Indenture”), among the Issuer, the Guarantors and Wells Fargo Bank, National Association, as trustee (the “Trustee”), as amended and supplemented by the First Supplemental Indenture thereto, to be dated as of January 22, 2013, among the Issuer, the Guarantors and the Trustee (the “Supplemental Indenture”).  The Subordinated Indenture, as amended and supplemented by the Supplemental Indenture, is referenced herein as the “Indenture.”  The Notes are being guaranteed on an unsecured and subordinated basis by the Guarantors pursuant to the guarantees included in the Indenture (the “Guarantees”), and are being sold by the Issuer to several underwriters pursuant to an Underwriting Agreement dated as of January 14, 2013 (the “Underwriting Agreement”) among the Issuer, the Partnership, NuPOP, Riverwalk Logistics, L.P., NuStar GP, LLC, NuStar GP, Inc. and NuStar Pipeline Company, LLC and Citigroup Global Markets Inc., RBC Capital Markets, LLC, UBS Securities LLC and Wells Fargo Securities, LLC as representatives of the several underwriters named therein.  The Issuer and the Guarantors are referred to collectively herein as the “Obligors.”

In rendering the opinions set forth herein, we have examined and relied on originals or copies, certified or otherwise identified to our satisfaction, of the following:

(i)                                     the registration statement on Form S-3 ASR (Registration No. 333-166797) filed by the Issuer with the United States Securities and Exchange Commission (the “SEC”) on May 13, 2010 (such registration statement, including the form of prospectus included therein and the documents incorporated by reference therein, being referred to herein as the “Registration Statement”);

NuStar Energy L.P.

January 17, 2013

Page 2

(ii)                                  the prospectus dated May 13, 2010, included in the Registration Statement, relating to the offering from time to time of certain securities of the Issuer and certain securities of the Guarantors (the “Base Prospectus”);

(iii)                               the preliminary prospectus supplement dated January 14, 2013, relating to the Notes, in the form filed on January 14, 2013 with the SEC, pursuant to Rule 424(b)(3) under the Securities Act of 1933, as amended (the “Securities Act”) (such prospectus supplement, together with the Base Prospectus, being referred to herein as the “Preliminary Prospectus”);

(iv)                              the term sheet dated January 14, 2013 relating to the Notes, filed on January 14, 2013 with the SEC as a free writing prospectus, pursuant to Rules 164 and 433 under the Securities Act;

(v)                                 the prospectus supplement dated January 14, 2013, relating to the Notes, in the form filed on January 15, 2013 with the SEC, pursuant to Rule 424(b)(5) under the Securities Act (such prospectus supplement, together with the Base Prospectus, being referred to herein as the “Prospectus”);

(vi)                              the Underwriting Agreement;

(vii)                           the Indenture;

(viii)                        the form of the Notes attached to the Supplemental Indenture;

(ix)                              the global note (the “Global Note”) to be executed by the Issuer pursuant to the Indenture, in the aggregate principal amount of $350,000,000, representing the Notes purchased and sold pursuant to the Underwriting Agreement;

(x)                                 the Certificate of Limited Partnership of the Partnership, and the Third Amended and Restated Agreement of Limited Partnership of the Partnership, in each case as amended to date;

(xi)                              the Certificate of Limited Partnership and the First Amended and Restated Limited Partnership Agreement of Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “General Partner”), in each case as amended to date;

(xii)                           the Certificate of Formation and the First Amended and Restated Limited Liability Company Agreement of NuStar GP, LLC, a Delaware limited liability company and the general partner of the General Partner (“GP, LLC”), in each case as amended to date;

NuStar Energy L.P.

January 17, 2013

Page 3

(xiii)                        resolutions of the Board of Directors of GP, LLC and resolutions of the Pricing Committee of the Board of Directors of GP, LLC certified by the Vice President and Corporate Secretary of GP, LLC;

(xiv)                       the Certificate of Limited Partnership of the Issuer and the Second Amended and Restated Agreement of Limited Partnership of the Issuer, in each case as amended to date;

(xv)                          the Certificate of Incorporation and the Bylaws of NuStar GP, Inc., a Delaware corporation and the general partner of the Issuer;

(xvi)                       the Certificate of Limited Partnership of NuPOP and the Amended and Restated Agreement of Limited Partnership of NuPOP, in each case as amended to date;

(xvii)                    the Certificate of Formation and the Amended and Restated Limited Liability Company Agreement of LegacyStar Services, LLC, a Delaware limited liability company and the 100% owner of NuStar Pipeline Company, LLC; and

(xviii)                 the Certificate of Formation and the Amended and Restated Limited Liability Company Agreement of NuStar Pipeline Company, LLC, a Delaware limited liability company and the general partner of NuPOP.

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Obligors and such agreements, certificates of public officials, certificates of officers or other representatives of the Obligors and others, and such other documents, certificates and records as we have deemed necessary or appropriate as a basis for the opinions set forth herein.

In our examination, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as certified, conformed or photostatic copies.  In making our examination of executed documents or documents to be executed, we have assumed that the parties thereto, other than the Obligors, had or will have the power, corporate or other, to enter into and perform all obligations thereunder and have also assumed the due authorization by all requisite action, corporate or other, and the due execution and delivery by such parties of such documents and, to the extent such documents purport to constitute agreements, such documents constitute valid and binding obligations of such parties.  As to any facts material to the opinions expressed herein that we have not independently established or verified, we have relied upon statements and representations of officers and other representatives of the Obligors and others.

We express no opinion other than as to the laws of the State of New York that are normally applicable to transactions of the type contemplated by the Underwriting Agreement, the Indenture and the Notes.

NuStar Energy L.P.

January 17, 2013

Page 4

Based upon the foregoing and subject to the limitations, qualifications, exceptions and assumptions set forth herein, we are of the opinion that when the Global Note (in the form examined by us) has been duly executed by the Issuer and authenticated by the Trustee in accordance with the terms of the Indenture and has been delivered in accordance with the terms of the Underwriting Agreement and the Indenture, the Notes will constitute valid and legally binding obligations of the Issuer, and the Guarantees will constitute valid and legally binding obligations of the Guarantors.

Our opinion above is subject to applicable bankruptcy, insolvency (including, without limitation, all laws relating to fraudulent transfer or conveyance), reorganization, moratorium and other similar laws affecting creditors’ rights generally and to general principles of equity (regardless of whether enforcement is sought in a proceeding in equity or at law), including, without limitation, (a) the possible unavailability of specific performance, injunctive relief or any other equitable remedy and (b) concepts of materiality, reasonableness, good faith and fair dealing, and we express no opinion herein with respect to provisions relating to severability or separability. Our opinion, insofar as it pertains to the choice of law provision of the Notes and the Indenture, is rendered solely in reliance upon New York General Obligations Law Section 5-1401, and is expressly conditioned upon the assumption that the legality, validity, binding effect and enforceability of said provision will be determined by a court of the State of New York or a United States federal court sitting in New York and applying New York choice of law rules, including said Section 5-1401. We express no opinion as to any constitutional limitations upon said Section 5-1401 or their effect, if any, upon any opinion herein expressed.

In rendering the opinion expressed above with respect to the Notes, we have assumed that the form and terms of the Notes, the issuance, sale and delivery thereof by the Issuer, and the incurrence and performance by the Obligors of their respective obligations under the Indenture and the incurrence and performance of the Issuer’s obligations under the Notes, in each case, will comply with, and will not violate, any applicable order, judgment, decree or award, or any contract, indenture, mortgage, loan agreement, note, lease or other agreement or instrument, in each case, binding upon any of the Obligors, or to which the issuance, sale and delivery of the Notes or the Guarantees, or the incurrence and performance of such obligations, may be subject.

We hereby consent to the filing of this opinion with the SEC as an exhibit to a Current Report of the Partnership on Form 8-K and to the reference to this firm under the heading “Legal Matters” in the Preliminary Prospectus and 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.