Exhibit 8.1

600 Travis, Suite 4200 Houston, Texas 77002 713.220.4200 Phone 713.220.4285 Fax andrewskurth.com

April 4, 2008

NuStar Energy L.P.

NuStar Logistics, L.P.

2330 N. Loop 1604 West

San Antonio, Texas 78248

Ladies and Gentlemen:

We have acted as special counsel in connection with (i) the preparation and filing with the Securities and Exchange Commission (the “Commission”) of the Registration Statement (SEC File 333-143095) on Form S-3 ASR filed by NuStar Energy L.P., a Delaware limited partnership (“NuStar Energy”), NuStar Logistics, L.P., a Delaware limited partnership (“NuStar Logistics”), and NuStar Pipeline Operating Partnership L.P. (formerly known as Kaneb Pipeline Operating Partnership, L.P.) (“NPOP”), under the Securities Act of 1933, as amended (the “Act”), on May 18, 2007 (the “Registration Statement”), for the purpose of registering under the Act, among other securities, debt securities of NuStar Logistics and (ii) the preparation of a prospectus supplement dated April 1, 2008 (the “Prospectus Supplement”) in connection with the offer and sale (the “Offering”) of $350,000,000 aggregate principal amount of NuStar Logistics’ 7.65% Senior Notes due 2018 (the “Notes”). The Notes are to be fully and unconditionally guaranteed (the “Guarantee” and, together with the Notes, the “Securities”) by NuStar Energy and NPOP (together, the “Guarantors”). In connection therewith, we have participated in the preparation of the discussion set forth under the caption “Material U.S. Federal Income Tax Considerations” (the “Discussion”) in the Prospectus Supplement.

The Discussion, subject to the qualifications and assumptions stated in the Discussion and the limitations and qualifications set forth herein, constitutes our opinion as to the material United States federal income tax consequences for purchasers of the Notes pursuant to the Offering.

This opinion letter is limited to the matters set forth herein, and no opinions are intended to be implied or may be inferred beyond those expressly stated herein. Our opinion is rendered as of the date hereof and we assume no obligation to update or supplement this opinion or any matter related to this opinion to reflect any change of fact, circumstances, or law after the date hereof. In addition, our opinion is based on the assumption that the matter will be properly presented to the applicable court.

Furthermore, our opinion is not binding on the Internal Revenue Service or a court. In addition, we must note that our opinion represents merely our best legal judgment on the matters

Austin     Beijing    Dallas    Houston    London    Los Angeles    New York    The Woodlands    Washington, DC

NuStar Energy L.P.

April 4, 2008

Page 2

presented and that others may disagree with our conclusion. There can be no assurance that the Internal Revenue Service will not take a contrary position or that a court would agree with our opinion if litigated.

We hereby consent to the filing of this opinion as an exhibit to a Current Report on Form 8-K of NuStar Energy and to the references to our firm and this opinion contained in the Prospectus Supplement forming a part of the Registration Statement. In giving this consent, we do not admit that we are “experts” under the Act or under the rules and regulations of the Commission relating thereto, with respect to any part of the Registration Statement, including this exhibit to the Current Report on Form 8-K.

Very truly yours,

/s/ Andrews Kurth LLP