EXHIBIT 5.1

600 Travis, Suite 4200 Houston, Texas 77002 713.220.4200 Phone 713.220.4285 Fax andrewskurth.com Austin Beijing Dallas Houston London Los Angeles New York The Woodlands Washington, DC

May 18, 2007

NuStar Energy L.P.

2330 N. Loop 1604 West

San Antonio, Texas 78248

Ladies and Gentlemen:

We have acted as special counsel to NuStar Energy L.P. (f/k/a Valero L.P.), a Delaware limited partnership (the “Partnership”), NuStar Logistics, L.P. (f/k/a Valero Logistics, L.P.), a Delaware limited partnership and wholly owned subsidiary of the Partnership (“NuStar Logistics”), and Kaneb Pipe Line Operating Partnership, L.P., a Delaware limited partnership and wholly owned subsidiary of the Partnership (“KPOP”), in connection with the preparation of a registration statement on Form S-3 (the “Registration Statement”), filed on May 16, 2007 with the Securities and Exchange Commission pursuant to the Securities Act of 1933, as amended (the “Securities Act”). As set forth in the Registration Statement and the form of prospectus contained therein (the “Prospectus”), the Registration Statement relates to the offer and sale from time to time, pursuant to Rule 415 under the Securities Act of the following securities, each on terms to be determined at the time of the offering thereof and to be described in a supplement to the Prospectus:

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

(ii) senior debt securities of NuStar Logistics (the “NuStar Logistics Senior Debt Securities”),

(iii) subordinated debt securities of NuStar Logistics (the “NuStar Logistics Subordinated Debt Securities” and collectively with the NuStar Logistics Senior Debt Securities, the “NuStar Logistics Debt Securities”),

(iv) senior debt securities of KPOP (the “KPOP Senior Debt Securities”),

(v) subordinated debt securities of KPOP (the “KPOP Subordinated Debt Securities” and collectively with the KPOP Senior Debt Securities, the “KPOP Debt Securities”), and

NuStar Energy L.P.

May 18, 2007

Page 2

(vi) guarantees by the Partnership and KPOP of the NuStar Debt Securities and guarantees by the Partnership and NuStar Logistics of the KPOP Debt Securities (all such guarantees being referred to herein as the “Guarantees”).

The NuStar Logistics Debt Securities and the KPOP Debt Securities are referred to collectively herein as the “Debt Securities”). The Common Units, the Debt Securities and the Guarantees are referred to collectively herein as the “Securities.”

The NuStar Logistics Senior Debt Securities will be issued in one or more series pursuant to the Indenture dated July 15, 2002 (filed as Exhibit 4.8 to the Registration Statement), as amended and supplemented by the First Supplemental Indenture dated July 15, 2002 filed as Exhibit 4.9 to the Registration Statement), and the Second Supplemental Indenture dated March 18, 2003 (filed as Exhibit 4.10 to the Registration Statement), in each case, among NuStar Logistics, the Partnership and The Bank of New York, as trustee, and as further amended and supplemented by the Third Supplemental Indenture dated July 1, 2005 (filed as Exhibit 4.11 to the Registration Statement), by and among NuStar Logistics, the Partnership, KPOP, as affiliate guarantor, and The Bank of New York Trust Company, N. A., as successor trustee (such indenture, as so amended and supplemented being referred to herein as the “NuStar Logistics Senior Indenture”). The NuStar Logistics Subordinated Debt Securities will be issued in one or more series pursuant to a subordinated indenture, substantially in the form attached as Exhibit 4.12 to the Registration Statement (the “NuStar Logistics Subordinated Indenture” and collectively with the NuStar Logistics Senior Indenture, the “NuStar Logistics Indentures”), to be entered into among NuStar Logistics, the Partnership and a trustee to be named therein.

The KPOP Senior Debt Securities will be issued in one or more series pursuant to the Indenture dated February 21, 2002 (filed as Exhibit 4.13 to the Registration Statement), as amended and supplemented by the First Supplemental Indenture dated February 21, 2002 (filed as Exhibit 4.14), the Second Supplemental Indenture dated August 9, 2002 (filed as Exhibit 4.15), the Third Supplemental Indenture dated May 16, 2003 (filed as Exhibit 4.16), and the Fourth Supplemental Indenture, dated May 27, 2003 (filed as Exhibit 4.17), in each case, between KPOP and JPMorgan Chase Bank, as trustee, and as further amended and supplemented by the Fifth Supplemental Indenture dated July 1, 2005, by and among KPOP, the Partnership, as affiliate guarantor, NuStar Logistics, as affiliate guarantor, and JPMorgan Chase Bank, as trustee (filed as Exhibit 4.18 to the Registration Statement) (such indenture, as so amended and supplemented being referred to herein as the “KPOP Senior Indenture”). The KPOP Subordinated Debt Securities will be issued in one or more series pursuant to a Subordinated Indenture, substantially in the form attached as Exhibit 4.19 to the Registration Statement (the “KPOP Subordinated Indenture” and collectively with the KPOP Senior Indenture, the “KPOP Indentures”) to be entered into between the KPOP, the Partnership and a trustee to be named therein.

The Guarantees of the NuStar Logistics Debt Securities issued under either of the NuStar Logistics Indentures will be issued under such indenture, as amended and supplemented by any supplemental indenture thereto, among (i) NuStar Logistics, as issuer, (ii) the Partnership and KPOP, as guarantors of such series of NuStar Logistics Debt Securities and (iii) the trustee under such indenture. The Guarantees of the KPOP Debt Securities issued under either of the KPOP

NuStar Energy L.P.

May 18, 2007

Page 3

Indentures will be issued under such indenture, as amended and supplemented by any supplemental indenture thereto, among (i) KPOP, as issuer, (ii) the Partnership and NuStar Logistics, as guarantors of such series of KPOP Debt Securities of such series and (iii) JPMorgan Chase Bank, as trustee under such indenture.

The NuStar Logistics Indentures and the KPOP Indentures are referred to collectively herein as the “Indentures.” Each of the Indentures has been filed as an exhibit to the Registration Statement, and pursuant to their respective terms, each may be supplemented from time to time, for various purposes, including in connection with the issuance of any series of Debt Securities and Guarantees thereof, if any.

In arriving at the opinions expressed below, we have examined the following:

(i) the Third Amended and Restated Agreement of Limited Partnership of the Partnership, as amended to date,

(ii) the Second Amended and Restated Agreement of Limited Partnership of NuStar Logistics, as amended to date,

(iii) the Reorganization Agreement of NuStar Logistics, dated as of May 30, 2002, among (a) NuStar Logistics, (b) the Partnership, (c) Riverwalk Logistics, L.P., a Delaware limited partnership and the general partner of the Partnership (the “MLP GP”) and (d) NuStar GP, Inc. (f/k/a Valero GP, Inc.), a Delaware corporation and the general partner of NuStar Logistics (the “NuStar Logistics GP”),

(iv) the Amended and Restated Agreement of Limited Partnership of KPOP, as amended to date,

(v) the Registration Statement,

(vi) the Prospectus,

(vii) the NuStar Logistics Senior Indenture,

(viii) the form of the NuStar Logistics Subordinated Indenture,

(ix) the KPOP Senior Indenture,

(x) the form of the KPOP Subordinated Indenture, and

(xi) the originals or copies certified or otherwise identified to our satisfaction of such other instruments and other certificates of public officials, officers and representatives of the Partnership and such other persons, and we have made such investigations of law, as we have deemed appropriate as a basis for the opinions expressed below.

In rendering the opinions expressed below, we have assumed and have not verified (i) the genuineness of the signatures on all documents that we have examined, (ii) the legal capacity of

NuStar Energy L.P.

May 18, 2007

Page 4

all natural persons, (iii) the authenticity of all the documents supplied to us as originals, and (iv) the conformity to the authentic originals of all documents supplied to us as certified or photostatic or faxed copies. In conducting our examination of documents, we have assumed the power (corporate, partnership, limited liability company or other) of all parties thereto (other than the Partnership, NuStar Logistics and KPOP) to enter into and perform all obligations thereunder and have also assumed the due authorization by all requisite action (corporate, partnership, limited liability company or other) and the due execution and delivery by such parties of such documents and that, except to the extent we expressly opine below, to the extent such documents purport to constitute agreements, such documents constitute valid and binding obligations of such parties.

In rendering the opinions expressed below with respect to the Securities, we have assumed that:

(i) the limited partnership agreements of the Partnership, NuStar Logistics and KPOP will not have been amended in any manner that would affect any legal conclusion set forth herein;

(ii) any supplemental indenture to any of the Indentures and/or any board resolution and/or any officer’s certificate executed and delivered pursuant to any of the Indentures, in any such case, pursuant to which any Debt Securities are issued, will comply with such Indenture as theretofore supplemented, and the form and terms of such Debt Securities (and related Guarantees, if any) will comply with such Indenture as then supplemented (including by such supplemental indenture) and with any such board resolution and/or officer’s certificate; and

(iii) the form and terms of the Debt Securities, when established, the form and terms of any Guarantees, and the form and terms of any and all Securities or other securities (or other obligations) comprising the same, the issuance, sale and delivery thereof by the Partnership, NuStar Logistics or KPOP, as the case may be, and the incurrence and performance of any issuer’s respective obligations thereunder or in respect thereof (including, without limitation, its obligations under any Indenture) in accordance with the terms thereof, will comply with, and will not violate, the applicable certificate of limited partnership or the applicable agreement of limited partnership of the Partnership, NuStar Logistics or KPOP, as the case may be, or any applicable law, rule, regulation, order, judgment, decree, award, or agreement binding upon the Partnership, NuStar Logistics and/or KPOP, or to which the issuance, sale and delivery of such Securities, or the incurrence and performance of such obligations, may be subject, or violate any applicable public policy, or be subject to any defense in law or equity, and (without limiting the generality of the foregoing) Section 5-501.6.b of the New York General Obligations Law will apply in the case of all such Debt Securities and Guarantees. In addition, except in the case of the Guarantees, we have assumed the receipt by each person to whom or for whose benefit a Security is to be issued (collectively, the “Beneficial Holders”) of a certificate for such Security or the receipt by The Depository Trust Company (or an agent thereof), acting as agent, on behalf of all Beneficial Holders of the class or series of Securities of which such Security is one, of a global security then evidencing such Securities, and the issuance and sale of and payment for the Securities so acquired, in accordance with (a) the applicable purchase, underwriting or similar agreement approved by the board of directors of the MLP GP, the board of directors of the

NuStar Energy L.P.

May 18, 2007

Page 5

NuStar Logistics GP and/or the board of directors of Kaneb Pipe Line Company, LLC, a Delaware limited liability company and the general partner of KPOP (the “KPOP GP”), and (b) the Registration Statement (including the Prospectus and the applicable Prospectus Supplement).

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

1. With respect to the Common Units, when (a) all necessary action (corporate, partnership, limited liability company or other) by or on behalf of the Partnership has been taken to approve the issuance of such Common Units, the terms of the offering thereof and related matters and (b) such Common Units have been issued and delivered as contemplated by the applicable definitive purchase, underwriting or similar agreement approved by the board of directors of the MLP GP, upon payment (or delivery) of the consideration therefor provided for therein, such Common Units will be validly issued, fully paid and non-assessable.

2. With respect to any series of NuStar Logistics Senior Debt Securities, to be issued under the NuStar Logistics Senior Indenture, when (a) the applicable supplemental indenture, if any, board resolutions and/or officer’s certificate, as the case may be, have been duly authorized and validly executed and delivered by or on behalf of the Partnership, NuStar Logistics, KPOP and the trustee, (b) the NuStar Logistics Senior Indenture, as then and theretofor supplemented, has been duly qualified under the Trust Indenture Act of 1939, as amended (the “Trust Indenture Act”), (c) all necessary action (corporate, partnership, limited liability company or other) by or on behalf of NuStar Logistics to approve the issuance and terms of such series of NuStar Logistics Senior Debt Securities, the terms of the offering thereof and related matters and (d) the NuStar Logistics Senior Debt Securities of such series have been duly executed, authenticated, issued and delivered in accordance with the terms of the NuStar Logistics Senior Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the board of directors of the NuStar Logistics GP, upon payment (or delivery) of the consideration therefor provided for therein, such series of NuStar Logistics Senior Debt Securities will be validly issued and will constitute valid and legally binding obligations of NuStar Logistics.

3. With respect to any series of NuStar Logistics Subordinated Debt Securities, to be issued under the NuStar Logistics Subordinated Indenture, when (a) the NuStar Logistics Subordinated Indenture, all then existing supplements thereto, and the applicable supplemental indenture, if any, board resolutions and/or officer’s certificate, as the case may be, have been duly authorized and validly executed and delivered by or on behalf of the Partnership, NuStar Logistics and the trustee, (b) the NuStar Logistics Subordinated Indenture, as then and theretofor supplemented, has been duly qualified under the Trust Indenture Act, (c) all necessary action (corporate, partnership, limited liability company or other) by or on behalf of NuStar Logistics to approve the issuance and terms of such series of NuStar Logistics Subordinated Debt Securities, the terms of the offering thereof and related matters and (d) the NuStar Logistics Subordinated Debt Securities of such series have been duly executed, authenticated, issued and delivered in accordance with the terms of the NuStar Logistics Subordinated Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the board of directors of the NuStar Logistics GP, upon payment (or delivery) of the consideration therefor provided for

NuStar Energy L.P.

May 18, 2007

Page 6

therein, such series of NuStar Logistics Subordinated Debt Securities will be validly issued and will constitute valid and legally binding obligations of NuStar Logistics.

4. With respect to any series of KPOP Senior Debt Securities, to be issued under the KPOP Senior Indenture, when (a) the KPOP Senior Indenture, all then existing supplements thereto, and the applicable supplemental indenture, if any, board resolutions and/or officer’s certificate, as the case may be, have been duly authorized and validly executed and delivered by or on behalf of the Partnership, KPOP and the trustee, (b) the KPOP Senior Indenture, as then and theretofor supplemented, has been duly qualified under the Trust Indenture Act, (c) all necessary action (corporate, partnership, limited liability company or other) by or on behalf of KPOP to approve the issuance and terms of such series of KPOP Senior Debt Securities, the terms of the offering thereof and related matters and (d) the KPOP Senior Debt Securities of such series have been duly executed, authenticated, issued and delivered in accordance with the terms of the KPOP Senior Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the board of directors of the KPOP GP, upon payment (or delivery) of the consideration therefor provided for therein, such series of KPOP Senior Debt Securities will be validly issued and will constitute valid and legally binding obligations of KPOP.

5. With respect to any series of KPOP Subordinated Debt Securities, to be issued under the KPOP Subordinated Indenture, when (a) the KPOP Subordinated Indenture, all then existing supplements thereto, and the applicable supplemental indenture, if any, board resolutions and/or officer’s certificate, as the case may be, have been duly authorized and validly executed and delivered by or on behalf of the Partnership, KPOP and the trustee, (b) the KPOP Subordinated Indenture, as then and theretofor supplemented, has been duly qualified under the Trust Indenture Act, (c) all necessary action (corporate, partnership, limited liability company or other) by or on behalf of KPOP to approve the issuance and terms of such series of KPOP Subordinated Debt Securities, the terms of the offering thereof and related matters and (d) the KPOP Subordinated Debt Securities of such series have been duly executed, authenticated, issued and delivered in accordance with the terms of the KPOP Subordinated Indenture and the applicable definitive purchase, underwriting or similar agreement approved by the board of directors of the KPOP GP, upon payment (or delivery) of the consideration therefor provided for therein, such series of KPOP Subordinated Debt Securities will be validly issued and will constitute valid and legally binding obligations of KPOP.

6. With respect to the Guarantees, when (a) all necessary action (corporate, partnership, limited liability company or other) has been taken by or on behalf of NuStar Logistics, the Partnership and KPOP to authorize and approve the issuance and terms of the Guarantees and the series of Debt Securities to which they pertain and the terms of the offering of such Debt Securities and such Guarantees and related matters, (b) the applicable Indenture, as then and theretofor supplemented, pursuant to which such Guarantees will be issued, has been duly qualified under the Trust Indenture Act, and (c) the Debt Securities of such series have been duly executed, issued, authenticated and delivered and such Guarantees have been duly executed, issued, authenticated and delivered, such Guarantees will constitute legal, valid and binding obligations of the applicable Guarantors, enforceable against the Guarantors in accordance with their terms.

NuStar Energy L.P.

May 18, 2007

Page 7

Our opinions in paragraphs 2, 3, 4, 5 and 6 above are 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.

We express no opinion other than the laws of the State of New York and the Delaware Revised Uniform Limited Partnership Act.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to this firm under the heading “Legal Matters” in the Prospectus. In giving this consent we do not admit that we are “experts” under the Securities Act, or the rules and regulations of the SEC thereunder, with respect to any part of the Registration Statement, including this exhibit. This opinion is expressed as of the date hereof, and we disclaim any undertaking to advise you of any subsequent changes of the facts stated or assumed herein or any subsequent changes in applicable law, and we have assumed that at no future time would any such subsequent change of fact or law affect adversely our ability to render at such time an opinion (a) containing the same legal conclusions set forth herein and (b) subject only to such (or fewer) assumptions, limitations and qualifications as are contained herein.

Very truly yours,

/s/ Andrews Kurth LLP