EXHIBIT 8.1

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

May 18, 2007

NuStar Energy, L.P.

2330 N. Loop 1604 West

San Antonio, Texas 78248

Re: NuStar Energy, L.P. Registration Statement on Form S-3

Gentlemen:

We have acted as special counsel to NuStar Energy, L.P., a Delaware limited partnership (the “Company”), in connection with the registration statement on Form S-3 (the “Registration Statement”) relating to the registration of the offering and sale (the “Offering”) of common units representing limited partner interests of the Company (the “Units”) and debt securities of each of NuStar Logistics, L.P., a Delaware limited partnership, and Kaneb Pipe Line Operating Partnership, L.P., a Delaware limited partnership, to be sold from time to time pursuant to Rule 415 of the Securities Act of 1933, as amended (the “Act”). In connection therewith, we have participated in the preparation of the discussion set forth under the caption “Material Tax Consequences” (the “Discussion”) in the Registration Statement.

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 Units 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 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.

NuStar Energy, L.P.

May 18, 2007

Page 2

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and to the references to our firm and this opinion contained in the Discussion. In giving this consent, we do not admit that we are “experts” under the Act or under the rules and regulations of the Securities and Exchange Commission relating thereto, with respect to any part of the Registration Statement.

Very truly yours,

/s/ ANDREWS KURTH LLP