NUSTAR SUPPLEMENTAL EXECUTIVE RETIREMENT PLAN

Exhibit 10.17

NUSTAR

SUPPLEMENTAL EXECUTIVE RETIREMENT PLAN

Amended and Restated Effective as of January 1, 2008

NUSTAR

SUPPLEMENTAL EXECUTIVE RETIREMENT PLAN

TABLE OF CONTENTS

NUSTAR

SUPPLEMENTAL EXECUTIVE RETIREMENT PLAN

The NuStar Supplemental Executive Retirement Plan, formerly known as the Valero GP, LLC Supplemental Executive Retirement Plan (hereinafter referred to as the “SERP” or the “Plan”), was established effective July 1, 2006 for the purpose of providing certain highly compensated, management personnel of NuStar GP LLC, formerly known as Valero GP, LLC, and its participating affiliates (hereinafter collectively referred to as the “Company”) a supplement to the retirement benefit they may otherwise receive under the NuStar Pension Plan (the “Pension Plan”) and the Valero Energy Corporation Pension Plan (“VEC Pension Plan”). The Plan is hereby amended and restated, effective as of January 1, 2008, in order to make certain amendments to the Plan necessary to comply with the provisions of Code Section 409A, and to make additional amendments to the Plan, all as set forth herein.

Benefits under the Plan are limited to a select group of management or other highly compensated employees specifically selected by the Committee for participation. The Plan is not intended to constitute either a qualified plan under the provisions of Section 401 of the Code or a funded plan subject to the Employee Retirement Income Security Act of 1974, as amended (“ERISA”).

The Plan was established in connection with a spin-off from the Valero Energy Corporation Supplemental Executive Retirement Plan (“VEC SERP”) of the benefits accrued under the VEC SERP with respect to Eligible Former VEC Employees (as defined below). In this connection, it is the intent of the Company that this Plan not constitute a new nonqualified deferred compensation plan, but rather an assumption and continuation of the portion of the Predecessor SERP spun-off and assumed by the Company, effective as of July 1, 2006, with respect to Eligible Employees of the Company who had accrued a benefit under the VEC SERP, and to provide benefits described herein to other Employees who become Participants hereunder.

1

The Company established the Pension Plan effective as of July 1, 2006, to provide defined benefit pension benefits to eligible Employees of the Company, with respect to future service. Effective as of July 1, 2006, eligible Employees of the Company ceased accruing additional benefits under the VEC Pension Plan and the VEC SERP. It is the intent of the Company that this Plan shall assume the liabilities of the VEC SERP with respect to Eligible Former VEC Employees, and shall provide a single, nonqualified defined benefit to Eligible Former Eligible VEC Employees for their pre-July 1, 2006 benefit accruals under the VEC SERP and their post-July 1, 2006 benefit accruals under this Plan, and that this Plan and the Company shall be solely liable for all benefits due Eligible Former VEC Employees under this Plan and the VEC SERP.

ARTICLE I

DEFINITIONS

All defined terms used in the Pension Plan shall have the same meaning in this Plan, except as otherwise set forth below. Additional terms are defined below.

1.1 Accrued Benefit. “Accrued Benefit” means, as of any given date of determination, the Retirement benefit of a Participant calculated under Section 4.1, offset by the aggregate accrued benefit, as of such date, for such Participant under the Pension Plan and the Prior Pension Plan.

1.2 Actuarial Equivalent or Actuarially Equivalent Basis. “Actuarial Equivalent” or “Actuarially Equivalent Basis” means an equality in value of the aggregate amounts expected to be received under different forms of payment based on the same mortality and interest rate assumptions. For this purpose, the mortality and interest rate assumptions used in computing benefits under the Pension Plan will be used. If, at any time, there is no Pension Plan, then the actuarial assumptions to be used for purposes of this Plan at such time will be those actuarial assumptions deemed appropriate by the actuarial firm selected for such purpose by the Committee.

2

1.3 Board of Directors. “Board of Directors” means the board of directors of the Company.

1.4 Change in Control. “Change in Control” shall mean the occurrence of one or more of the following events:

(a) Any one person or more than one person acting as a group (a “Group”) shall acquire (whether in one or more transactions) ownership of interests in the Company that, together with interests held by such person or Group, constitutes more than 50% of the total fair market value or total voting power of all interests, of the Company; or

(b) any one person or Group acquires (or has acquired during the 12-month period ending on the date of the most recent acquisition by such person or Group) ownership interests in the Company representing 30% or more of the total voting power of all such interests in the Company; or

(c) a majority of the members of the governing body of the Company is replaced during any 12-month period by members whose appointment or election is not endorsed by a majority of the members of the governing body of the Company prior to the date of appointment or election; or

(d) any one person or Group acquires (or has acquired during the 12-month period ending on the date of the most recent acquisition by such person or Group) assets from the Company that have a total gross fair market value equal to or more than 40% of the total gross fair market value of all of the assets of the Company immediately prior to such acquisition or acquisitions.

The provisions of this Excess Thrift Plan relating to a Change in Control shall be interpreted and administered in a manner consistent with Code Section 409A and the regulations and additional guidance thereunder.

In determining whether a Change in Control occurs, the final regulations under Code Section 409A are intended to control and this Plan shall be administered consistently therewith.

1.5 Code. “Code” means the Internal Revenue Code of 1986, as amended from time to time.

1.6 Company. “Company” means NuStar GP, LLC and any successor by merger, purchase or otherwise.

1.7 Committee. “Committee” means the Benefit Plans Administrative Committee designated by the board of directors of the Company.

1.8 Covered Compensation. “Covered Compensation” means the average (without indexing) of the Taxable Wage Base for the 35 calendar years ending with the calendar year in which a Participant attains social security retirement age (as defined in Code Section 415(b)(8)).

3

A 35-year period shall be used for all Participants regardless of the year of birth of such Participant. In determining a Participant’s Covered Compensation prior to the Participant attaining social security retirement age, it shall be assumed that the Taxable Wage Base in effect at the beginning of the Plan Year in which such determination is made will remain constant for all future years.

1.9 Credited Service. “Credited Service” means a Participant’s continuing period of employment with the Company (whether or not contiguous), commencing on the first day for which such Participant is paid, or entitled to payment, for the performance of duties with the Company and terminating with the Participant’s final cessation of participation in the Plan. With respect to any full calendar year in which a Participant receives Eligible Earnings in each payroll period as an active Employee, he shall be credited with one year of Credited Service. With respect to any partial calendar year in which a Participant receives Eligible Earnings as an active Employee (such as the calendar year in which employment commences or participation ceases) he shall be credited with a fraction of a year of Credited Service, in the same proportion that the number of payroll periods during such calendar year that he received Eligible Earnings as an active Employee bears to the total number of payroll periods during such year. All partial years of Credited Service shall be aggregated so that a Participant receives credit for all periods of employment regardless of whether the Credited Service is interrupted. Credited Service shall also include, and a Participant shall be credited with, such additional periods of time, if any, as may have been agreed upon by the Participant and the Company in connection with the Participant’s employment, termination or otherwise. For Eligible Former VEC Employees, Credited Service shall also include the service credited for such Employees for benefit accrual purposes under the Valero Energy Corporation Pension Plan. Notwithstanding any other provision of this Plan, for purposes of calculating a Participant’s benefit hereunder, Credited Service shall not include any period of service for which a Participant has received a payment, or is receiving payments, under this Plan, or, for Former Eligible VEC Employees, any period of service for which a Participant has received or is receiving payments under the Excess Pension Plan, the VEC Excess Pension Plan, the VEC SERP, the Ultramar Diamond Shamrock Corporation Supplemental Executive Retirement Plan, or a lump sum payment made prior to January 1, 2002 under the Ultramar Diamond Shamrock Corporation Employees’ Retirement Plan.

1.10 Disability. “Disabled” or “Disability” shall mean the existence of one or more of the following conditions:

4

1.11 Eligible Earnings. “Eligible Earnings” means all compensation paid or payable by the Company to the employee in the form of base salary or wages and bonuses (whether paid or payable in cash or securities or any combination thereof), including therein any amounts of such base salary or wages and bonuses earned which, at the employee’s election, in lieu of a cash payment to him, are contributed to a Plan of Deferred Compensation maintained by the Company, if any. During an approved leave of absence from work without pay, the Participant’s base rate of pay in effect immediately prior to the leave of absence and his/her most recent annual bonus amount paid shall be used in computing his Eligible Earnings.

1.12 Eligible Former VEC Employee. “Eligible Former VEC Employee” shall mean an individual who: (a) became an Employee on or before December 31, 2008; (b) becomes a Participant hereunder; (c) was employed by VEC, or an affiliate of VEC, at any time from and after July 1, 2005; and (d) participated in the VEC Pension Plan.

1.13 Excess Pension Plan. “Excess Pension Plan” means the NuStar Excess Pension Plan, as it may be amended from time to time and any successor plan thereto.

1.14 Final Average Compensation. “Final Average Compensation” means a Participant’s average monthly Eligible Earnings from the Company, and from Valero Energy Corporation prior to the Effective Date of this Plan, for the thirty-six consecutive calendar months that give the highest average monthly rate of Eligible Earnings for the Participant out of all calendar months next preceding the earliest of (a) the date upon which a Participant becomes ineligible for participation in this Plan, (b) the Participant’s Separation from Service, (c) the termination of this Plan, or (d) a Change in Control.

1.15 Monthly Covered Compensation. “Monthly Covered Compensation” means the quotient resulting from dividing Covered Compensation by 12.

1.16 Monthly FICA Amount. “Monthly FICA Amount” means the quotient resulting from dividing by 12 the Taxable Wage Base in effect or assumed to be in effect at the beginning of the calendar year in which a Participant attains social security retirement age (as defined in Code Section 415(b)(8)).

1.17 Normal Retirement Date. “Normal Retirement Date” means the first day of the month coincident with or next following the date on which the Participant attains the age of 65 years.

1.18 Participant. “Participant” means either (a) an employee of the Company who is eligible for and is participating in the Plan or (b) a former employee of the Company who is receiving, or is eligible to receive benefits under the Plan.

1.19 Pension Plan. “Pension Plan” means the NuStar Pension Plan, a defined benefit plan qualified under Section 401(a) of the Code, as it may be amended from time to time and any successor qualified defined benefit pension plan.

1.20 Pension Plan Benefit. “Pension Plan Benefit” means the amount of monthly benefit payable from the Pension Plan which (i) in the case of an unmarried Participant, is based upon a lifetime annuity payable to such Participant pursuant to the provisions of Article 4 of the

5

Pension Plan, or any successor provision; or, (ii) in the case of a married Participant, is based upon a joint and survivor pension of Actuarially Equivalent Value to the pension otherwise payable to such Participant for life pursuant to the provisions of Article 4 of the Pension Plan or any successor provision.

1.21 Plan. “Plan” means the NuStar Supplemental Executive Retirement Plan, as set forth in this document, and as amended from time to time.

1.22 Plan of Deferred Compensation. “Plan of Deferred Compensation” means any non-qualified deferred compensation plan or arrangement, any Code Section 125 cafeteria plan, or any Code Section 401(k) cash or deferred arrangement maintained by the Company.

1.23 Plan Year. “Plan Year” means the calendar year.

1.24 Rules. “Rules” means the Commercial Arbitration Rules of the American Arbitration Association in effect at the date of commencement of any arbitration hereunder.

1.25 Securities Exchange Act. “Securities Exchange Act” means the Securities Exchange Act of 1934, as amended from time to time.

1.26 Separation from Service. “Separation from Service” shall mean a separation from service as defined in Code Section 409A and the regulations and rulings issued thereunder.

1.27 Subsidiary. “Subsidiary” means (i) any corporation 50% or more of whose stock having ordinary voting power to elect directors (irrespective of whether or not at the time stock of any class or classes of such corporation shall have or might have voting power by reason of the happening of any contingency) is at the time owned, directly or indirectly, by the Company, and (ii) any partnership, association, joint venture or other entity in which, the Company, directly or indirectly, has a 50% or greater equity interest at the time.

1.28 Surviving Spouse. “Surviving Spouse” means the spouse of a Participant who is eligible to receive a Qualified Pre-retirement Survivor Annuity benefit under the Pension Plan.

1.29 Trust. “Trust” or “Trust Agreement” shall mean the trust, if any, created to fund benefits under the Plan pursuant to Article X.

1.30 Trustee. “Trustee” means the trustee appointed by the Committee, which has accepted the duties of Trustee of the Trust (if any), and any successor trustee appointed by the Committee.

1.31 VEC. “VEC” means Valero Energy Corporation, or any successor entity.

1.32 VEC Pension Plan. “VEC Pension Plan” means the Valero Energy Corporation Pension Plan, as amended from time to time, and any successor defined benefit pension plan.

1.33 VEC Pension Plan Benefit. “VEC Pension Plan Benefit” means the amount of the benefit payable from the VEC Pension Plan to a Participant, which (i) in the case of an unmarried Participant, is based upon a lifetime annuity payable to such Participant pursuant to

6

the provisions of Article 4 of the VEC Pension Plan, or any successor provision; or, (ii) in the case of a married Participant, is based upon a joint and survivor pension of Actuarially Equivalent Value to the pension otherwise payable to such Participant for life pursuant to the provisions of Article 4 of the VEC Pension Plan or any successor provision.

1.34 VEC SERP. “VEC SERP” means the Valero Energy Corporation Supplemental Executive Retirement Plan, as amended from time to time, and any successor plan.

ARTICLE II

ELIGIBILITY

2.1 Eligibility. Any Employee who was (a) an Employee on the Effective Date, and