Exhibit 4.03

Amendment No. 2

to

Rights Agreement

of NuStar GP Holdings, LLC

(f/k/a Valero GP Holdings, LLC)

This Amendment No. 2 (this “Amendment”), to the Rights Agreement, dated as of July 19, 2006, between NuStar GP Holdings, LLC (f/k/a Valero GP Holdings, LLC), a Delaware limited liability company (the “Company”), and Computershare Trust Company, N.A., successor rights agent to Computershare Investor Services, LLC (the “Rights Agent”), as amended by that certain Amendment No. 1 to the Rights Agreement entered into effective as of February 28, 2008 (as so amended, the “Rights Agreement”) is entered into effective as of October 23, 2012 by and between the Company and the Rights Agent. Capitalized terms used but not defined herein are used as defined in the Rights Agreement.

RECITALS

WHEREAS, pursuant to and in compliance with Section 27 of the Rights Agreement, the Company and the Rights Agent wish to amend the Rights Agreement as set forth herein;

WHEREAS, the Company deems it in the best interest of the Company to effect this Amendment in order to amend Section 1 of the Rights Agreement;

NOW, THEREFORE, in light of the foregoing, it is hereby agreed as follows:

AMENDMENT

1.             Section 1 of the Rights Agreement shall be amended to amend and restate the definition of “Exempt Person” in its entirety as follows:

“ “Exempt Person” shall mean (i) William E. Greehey, unless such Person shall become the Beneficial Owner of any Company Securities other than (a) 6,116,643 Units (appropriately adjusted for any unit split, reverse unit split or distribution) owned on February 28, 2008 (the “Greehey Original Units”), plus (b) such number of additional Units (appropriately adjusted for any unit split, reverse unit split or distribution) which, together with the Greehey Original Units, shall be less than 20% of the Units of the Company then outstanding and (ii) Neuberger Berman Group LLC, unless such Person shall become the Beneficial Owner of any Company Securities other than (x) 6,208,544 Units (appropriately adjusted for any unit split, reverse unit split or distribution) beneficially owned on June 30, 2012 (the “NBG Original Units”), plus (y) such number of additional Units (appropriately adjusted for any unit split, reverse unit split or distribution) which, together with the NBG Original Units, shall be less than 17.5% of the Units of the Company then outstanding. A purchaser, assignee or transferee of Units from an Exempt Person shall not thereby become an Exempt Person, except that a transferee from the estate of an Exempt Person who receives Units as a bequest or inheritance from an Exempt Person shall be an Exempt Person so long as such Person continues to be the Beneficial Owner of 15% or more of the then outstanding Units.”

2.             This Amendment may be executed in counterparts, each of which shall be deemed an original, but all of which shall constitute one and the same instrument.  A signature to this Amendment transmitted electronically shall have the same authority, effect, and enforceability as an original signature.

3.             Except as hereby amended, the Rights Agreement shall remain in full force and effect.

4.             This Amendment shall be governed by, and interpreted in accordance with, the laws of the State of Delaware.

5.             Each provision of this Amendment shall be considered severable and if for any reason any provision or provisions herein are determined to be invalid, unenforceable or illegal under any existing or future law, such invalidity, unenforceability or illegality shall not impair the operation of or affect those portions of this Amendment that are valid, enforceable and legal.

[REMAINDER OF THIS PAGE INTENTIONALLY LEFT BLANK]

2

IN WITNESS WHEREOF, the parties hereto have caused this Amendment to be duly executed and attested, all as of the day and year first above and written.

3