INSTRUMENT OF RESIGNATION, APPOINTMENT AND ACCEPTANCE

Exhibit 4.12

INSTRUMENT OF RESIGNATION,

APPOINTMENT AND ACCEPTANCE

INSTRUMENT OF RESIGNATION, APPOINTMENT AND ACCEPTANCE (this “Agreement”) entered into as of June 30, 2008 among NuStar Pipeline Operating Partnership L.P. (formerly known as Kaneb Pipe Line Operating Partnership, L.P.), a Delaware limited partnership (the “Partnership”), NuStar Energy L.P. (formerly known as Valero L.P.), a Delaware limited partnership (“NuStar”), NuStar Logistics, L.P. (formerly known as Valero Logistics Operations, L.P.), a Delaware limited partnership (“Logistics” and, together with NuStar, “Affiliate Guarantors”), The Bank of New York Trust Company, N.A., as successor trustee to JPMorgan Chase Bank, National Association, a national banking association (the “Resigning Trustee”) and Wells Fargo Bank, National Association, a national banking association organized and existing under the laws of the United States of America (the “Successor Trustee”).

W I T N E S S E T H

WHEREAS, the Partnership and Resigning Trustee have entered into the Indenture, dated as of February 21, 2002 (the “Original Indenture”), as amended and supplemented by (i) the First Supplemental Indenture thereto dated as of February 21, 2002 (the “First Supplemental Indenture”), (ii) the Second Supplemental Indenture thereto dated as of August 9, 2002 and effective as of April 4, 2002 (the “Second Supplemental Indenture”), (iii) the Third Supplemental Indenture thereto dated and effective as of May 16, 2003 (the “Third Supplemental Indenture”), (iv) the Fourth Supplemental Indenture thereto dated as of May 27, 2003 (the “Fourth Supplemental Indenture”), and (v) the Fifth Supplemental Indenture thereto dated as of July 1, 2005 among the Partnership, the Affiliate Guarantors and Resigning Trustee (the “Fifth Supplemental Indenture”) (the Original Indenture, as supplemented from time to time, including without limitation pursuant to the First Supplemental Indenture, the Second Supplemental Indenture, the Third Supplemental Indenture, the Fourth Supplemental Indenture, and the Fifth Supplemental Indenture, the “Indenture”), which provides for the issuance of the Partnership’s securities, the outstanding series of which are set forth on Exhibit A hereto (collectively, the “Debt Securities”); and

WHEREAS, Resigning Trustee has been acting as Trustee under the Indenture with respect to all Securities; and

WHEREAS, Section 7.08 of the Indenture provides that Resigning Trustee may resign with respect to the Debt Securities at any time by giving notice thereof to the Partnership; and

WHEREAS, Section 7.08 of the Indenture provides that the Partnership shall promptly appoint a successor Trustee to fill a vacancy in the office of Trustee under the Indenture; and

WHEREAS, Section 7.08 of the Indenture provides that any successor Trustee appointed in accordance with the Indenture shall execute, acknowledge and deliver to the Partnership and the retiring Trustee an instrument accepting such appointment under the Indenture, and thereupon the resignation of the retiring Trustee shall become effective and such successor Trustee shall become vested with all rights, powers, trusts and duties of the retiring Trustee under the Indenture; and

WHEREAS, the Partnership wishes to appoint Successor Trustee as successor Trustee under the Indenture to succeed Resigning Trustee in such capacities; and

WHEREAS, Successor Trustee is willing to accept such appointment as successor Trustee, Security Registrar and Paying Agent under the Indenture on the terms and conditions set forth herein and under the Indenture; and

WHEREAS, Successor Trustee is eligible to act as successor Trustee under the Indenture;

NOW, THEREFORE, pursuant to the provisions of the Indenture and in consideration of the covenants herein contained, it is agreed among the Partnership, the Affiliate Guarantors, Resigning Trustee and Successor Trustee as follows:

1. Pursuant to Section 7.08 of the Indenture, Resigning Trustee hereby resigns as Trustee under the Indenture with respect to all Debt Securities.

2. Resigning Trustee hereby assigns, transfers, delivers and confirms to Successor Trustee all rights, powers, duties, trusts and obligations of the Trustee under the Indenture with respect to all Debt Securities.

3. Resigning Trustee represents and warrants to Successor Trustee that Resigning Trustee will promptly deliver the original Debt Securities to Successor Trustee, and will, upon Successor Trustee’s request, use reasonable commercial efforts to make available to Successor Trustee such originals, if available, or copies of material documentation relating to the Indenture, its administration and status as are available on Resigning Trustee’s electronic document imaging system or are in the possession of the relationship manager of the Resigning Trustee responsible for this matter, but only to the extent that such documentation is not otherwise available to Successor Trustee from the Partnership, Depositary Trust Corporation or from public sources.

4. The Partnership hereby accepts the resignation of Resigning Trustee as Trustee with respect to all Debt Securities under the Indenture. Pursuant to the authority vested in it by Section 7.08 of the Indenture, the Partnership hereby appoints Successor Trustee as successor Trustee under the Indenture with respect to all Debt Securities, with all the rights, powers, trusts and duties heretofore vested in Resigning Trustee under the Indenture.

5. The Partnership represents and warrants to Resigning Trustee and Successor Trustee that:

(a) it is validly organized and existing under the laws of the state of its formation;

(b) the Debt Securities were validly and lawfully issued;

(c) it has performed or fulfilled each covenant, agreement and condition on its part to be performed or fulfilled under the Indenture;

(d) no default or Event of Default or any event which upon notice or lapse of time or both would become and Event of Default under the Indenture has occurred and is continuing;

(e) it has not appointed any Security Registrar or Paying Agent under the Indenture other than Resigning Trustee; and

(f) it will continue to perform the obligations undertaken by it under the Indenture.

6. Successor Trustee represents and warrants to Resigning Trustee and the Partnership that it is qualified and eligible to act as Trustee under Article VII of the Indenture.

7. Successor Trustee hereby accepts its appointment as successor Trustee with respect to all Debt Securities, Securities Registrar and Paying Agent under the Indenture, and accepts the obligations created thereby, and assumes all rights, powers, duties and obligations of the Trustee, Securities Registrar and Paying Agent under the Indenture. Successor Trustee will perform said obligations and will exercise said rights, powers, duties and obligations upon the terms and conditions set forth in the Indenture.

8. Successor Trustee hereby accepts the designation of its Corporate Trust Office as the office or agency of the Partnership in Dallas, Texas where the Debt Securities may be presented for payment or registration of transfer.

9. Promptly after the execution and delivery of this Agreement, the Successor Trustee will mail or cause to be mailed to each holder of the Debt Securities a Notice of Succession of Trustee, a form of which is attached hereto as Exhibit B in accordance with Section 7.08 of the Indenture.

10. Pursuant to the written request of Successor Trustee and the Partnership hereby made, Resigning Trustee, upon payment of its outstanding charges, confirms, assigns, transfers and sets over to Successor Trustee, as successor Trustee under the Indenture, upon the obligations expressed in the Indenture, any and all property and money and all the rights, powers, trusts, duties and obligations which Resigning Trustee now holds under and by virtue of the Indenture.

11. The Partnership and Resigning Trustee hereby agree, upon the request of Successor Trustee, to execute, acknowledge and deliver such further instruments of conveyance and assurance and to do such other things as may be reasonably required for more fully and certainly vesting and confirming in Successor Trustee all of the applicable rights, powers and trusts of Resigning Trustee as Trustee under the Indenture.

12. Capitalized terms not otherwise defined in this Agreement shall have the definitions given thereto in the Indenture.

13. This Agreement shall be governed by and construed in accordance with the laws of the State of New York.

14. In case any provision in this Agreement shall be invalid, illegal or unenforceable, the validity, legality and enforceability of the remaining provisions shall not in any way be affected or impaired thereby.

15. This Agreement may be simultaneously executed in any number of counterparts. Each such counterpart so executed shall be deemed to be an original, but all together shall constitute but one and the same instrument.

16. This Agreement and the resignation, appointment and acceptance effected hereby shall be effective as of the close of business on the date first above written, upon the execution and delivery hereof by each of the parties hereto, and any and all payments required to be made by the Trustee under the Indenture shall be made by Successor Trustee following such effectiveness.

17. Notwithstanding the resignation of Resigning Trustee effected hereby, the Partnership shall remain obligated under Section 7.08 of the Indenture to compensate, reimburse and indemnify Resigning Trustee in connection with its prior trusteeship under the Indenture. The Partnership also acknowledges and reaffirms its obligations to Successor Trustee as set forth in Section 7.06 of the Indenture, which obligations shall survive the execution hereof.

18. All notices, whether faxed or mailed, will be deemed received when sent pursuant to the following instructions:

TO RESIGNING TRUSTEE:

The Bank of New York Trust Company, N.A.

601 Travis Street, 18^th Floor

Houston, Texas 77002

Tel: 713 ###-###-####

Fax: 713 ###-###-####

Attn: Julie Hoffman-Ramos

TO SUCCESSOR TRUSTEE:

Wells Fargo Bank, National Association

1445 Ross Avenue – 2^nd Floor

Corporate Trust Services

Dallas, Texas ###-###-####

Fax: 214 ###-###-####

Tel: 214 ###-###-####

Attn: Patrick Giordano- Vice President

TO THE PARTNERSHIP:

Amy L. Perry

Assistant General Counsel

NuStar Energy L.P.

2330 North Loop 1604 West

San Antonio, Texas 78248

Fax: (210) 918-5469

Tel: (210) 918-2512

[remainder of page intentionally blank]

IN WITNESS WHEREOF, the parties hereto have caused this Instrument of Resignation, Appointment and Acceptance to be duly executed as of the day and year first above written.

EXHIBIT A

CHART OF OUTSTANDING DEBT SECURITIES

EXHIBIT B

NOTICE OF SUCCESSION OF TRUSTEE

To the Holders of NuStar Pipeline Operating Partnership L.P.’s (the “Partnership”)

(collectively, the “Debt Securities”)

NOTICE IS HEREBY GIVEN that, pursuant to Section 7.08 of the Indenture, dated as of February 21, 2002 (the “Original Indenture”), as amended and supplemented by (i) the First Supplemental Indenture thereto dated as of February 21, 2002 (the “First Supplemental Indenture”), (ii) the Second Supplemental Indenture thereto dated as of August 9, 2002 and effective as of April 4, 2002 (the “Second Supplemental Indenture”), (iii) the Third Supplemental Indenture thereto dated and effective as of May 16, 2003 (the “Third Supplemental Indenture”), (iv) the Fourth Supplemental Indenture thereto dated as of May 27, 2003 (the “Fourth Supplemental Indenture”), and (v) the Fifth Supplemental Indenture thereto dated as of July 1, 2005 (the “Fifth Supplemental Indenture”) (the Original Indenture, as supplemented from time to time, including without limitation pursuant to the First Supplemental Indenture, the Second Supplemental Indenture, the Third Supplemental Indenture, the Fourth Supplemental Indenture, and the Fifth Supplemental Indenture, the “Indenture”), under which the above mentioned Debt Securities were issued, The Bank of New York Trust Company, N.A., as successor to JPMorgan Chase Bank, National Association, a national banking association, has resigned as Trustee.

NOTICE IS HEREBY FURTHER GIVEN that pursuant to Section 7.08 of the Indenture, the Partnership has appointed Wells Fargo Bank, National Association, a national banking association organized and existing under the laws of the United States of America, as successor Trustee under the Indenture. Wells Fargo Bank, National Association has, pursuant to Section 7.08 of the Indenture, accepted such appointment, effective as of June 30, 2008. The address of the Corporate Trust Office of Wells Fargo Bank, National Association is 1445 Ross Avenue-2nd Floor Dallas, Texas ###-###-####, Attn: Corporate Trust Services.

Dated:                     , 2008