THIRD AMENDED AND RESTATED SERVICES AGREEMENT

Exhibit 10.01

THIRD AMENDED AND RESTATED

SERVICES AGREEMENT

AMONG

DIAMOND SHAMROCK REFINING AND MARKETING COMPANY

VALERO CORPORATE SERVICES COMPANY

VALERO L.P.

VALERO LOGISTICS OPERATIONS, L.P.

RIVERWALK LOGISTICS, L.P.

AND

VALERO GP, L.L.C.

DATED AS OF JANUARY 1, 2006

THIRD AMENDED AND RESTATED SERVICES AGREEMENT

This THIRD AMENDED AND RESTATED SERVICES AGREEMENT (this “Agreement”) is entered into effective as of January 1, 2006 (the “Effective Date”) by and among DIAMOND SHAMROCK REFINING AND MARKETING COMPANY, a Delaware corporation (“DSRMC”) and VALERO CORPORATE SERVICES COMPANY, a Delaware corporation (“VSCS”), both indirect wholly owned subsidiaries of Valero Energy Corporation (“Valero Energy”), VALERO L.P., a publicly traded Delaware limited partnership (the “Partnership”), VALERO LOGISTICS OPERATIONS, L.P. (the “Operating Partnership”), a Delaware limited partnership and an indirect wholly owned subsidiary of the Partnership, RIVERWALK LOGISTICS, L.P., the general partner (the “General Partner”) of the Partnership, and its general partner, VALERO GP, LLC (“Valero GP”).

RECITALS

WHEREAS, certain parties hereto entered into a Services Agreement effective July 1, 2000 pursuant to which DSRMC agreed to provide certain corporate, general and administrative services to the General Partner in exchange for an administrative services fee; and

WHEREAS, the Services Agreement was amended and restated (the “First Amended and Restated Services Agreement”) effective April 1, 2004; and

WHEREAS, on July 1, 2005, the Partnership completed its acquisition of Kaneb Services, LLC and Kaneb Pipe Line Partners, L.P., effectively doubling the Partnership’s operations; and

WHEREAS, the Services Agreement was amended and restated as of July 1, 2005 (the “Second Amended and Restated Services Agreement”) to reflect the significant changes in operations that resulted from the acquisition; and

WHEREAS, management of the General Partner has determined that some of the services currently being provided by affiliates of Valero Energy under the Second Amended and Restated Services Agreement should be performed by the Partnership Parties and has determined that the Second Amended and Restated Services Agreement should be further amended to more accurately reflect the provision of the corporate, general and administrative services;

WHEREAS, on January 26, 2006, upon recommendation by management of the General Partner and the Conflicts Committee of the Board of Directors of the General Partner, the Board of Directors of the General Partner approved the terms of this Agreement; and

WHEREAS, VCSC, for itself and its Affiliates, has agreed to provide certain administrative services under this Agreement to Valero GP, the General Partner, the Partnership and the Operating Partnership (individually, a “Partnership Party,” and collectively, the “Partnership Parties”); and

NOW, THEREFORE, for and in consideration of the mutual covenants contained in this Agreement, the parties hereto hereby agree to amend and restate the Amended and Restated Services Agreement as follows:

ARTICLE I

PROVISION OF SERVICES

Section 1.1 Provision of Administrative Services by VCSC and its Affiliates.

(a) Administrative Services. VCSC or any Affiliate or designee of VCSC shall provide to the Partnership Parties certain non-exclusive management, employee-related and other services as set forth on Exhibit A hereto, and such other services as VCSC and Valero GP may from time to time agree (the “Administrative Services”).

For purposes of this Agreement, “Affiliates” means entities that directly or indirectly through one or more intermediaries control, or are controlled by, or are under common control with, such party, and the term “control” shall mean the possession, directly or indirectly, of the power to direct or cause the direction of management and policies of an entity, whether through the ownership of voting securities, by contract or otherwise, provided, however, that with respect to VCSC or Valero Energy, the term “Affiliate” shall exclude Valero GP Holdings, LLC, Valero GP, the General Partner, the Partnership and the Operating Partnership.

(b) Telecommunications Services. VCSC or any Affiliate of VCSC shall provide the Partnership Parties with Telecommunication Services substantially similar to those provided to Affiliates of VCSC during the term of this Agreement. Telecommunications Services shall include costs of circuits related to telecommunications hardware, cell phones, Blackberries (or their functional equivalent) and other personal communications devices, and local and long distance carrier service.

(c) Additional Services. VCSC or any Affiliate of VCSC shall provide the Partnership Parties with such other services as Valero GP may request from time to time during the term of this Agreement and for such additional compensation as the parties may agree.

(d) Direct Charges. Notwithstanding Section 1.1 (a) above, the following items will be directly charged to the Partnership (“Direct Charges”):

all third party expenses directly related to the Partnership Parties, including, but not limited to, public company costs, outside legal fees, outside accounting fees, fees and expenses of external advisors and consultants, and insurance costs, including but not limited to, general liability, automobile liability, comprehensive liability, excess liability, property and directors and officers.

(d) Nature and Quality of Services. The quality of the Administrative Services and the Telecommunications Services shall be substantially identical to those provided to other subsidiaries and Affiliates of VCSC.

Section 1.2 Fees for Administrative Services.

(a) Commencing on the Effective Date of this Agreement, and for each contract year thereafter, the Partnership shall pay to VCSC an annual fee (the “Administrative Services Fee”). The Administrative Services Fee for the contract year ended December 31, 2006 shall be $765,000, for the contract year ended December 31, 2007 shall be $1.765 million, and thereafter such fee shall be $2.265 million for the contract year ended December 31, 2008 and the years following, subject to adjustment as provided in paragraph (b) below.

2

(b) On the last day of each contract year starting with the contract year ending December 31, 2006, and prior to the beginning of the next contract year, the Administrative Services Fee shall be increased by an amount equal to Valero Energy’s general annual merit increase percentage for the just completed contract year.

(c) The General Partner, with the approval and consent of the Conflicts Committee, may agree on behalf of the Partnership to further modifications in the Administrative Services Fee in connection with changed levels of Administrative Services provided to the Partnership Parties due to expansions of the Partnership’s operations through acquisition or construction of new assets or businesses.

(d) At the end of each contract year, the scope of the Administrative Services and the related Administrative Services Fee are subject to review either at the request of VCSC or the Partnership Parties, in either case by providing 10 days written notice to the other party but in no event later than 60 days before the end of the applicable contract year, with such review to be completed no later than March 31 of the immediately following contract year, with any modification of the Administrative Services Fee other than as provided in paragraphs (a) and (b) above subject to the consent and approval of the Conflicts Committee.

(e) Any fees payable hereunder for periods less than a full contract year shall be prorated for the period services were provided based on the actual number of days elapsed and a year of 365 days.

(f) The Partnership shall pay all applicable sales taxes on the portion of the Administrative Services Fee attributable to IS Support.

Section 1.3 Fees for Telecommunications Services.

Commencing on the Effective Date of this Agreement, and for each contract year thereafter, the Partnership shall pay to VCSC an annual fee for the provision of the Telecommunications Services (the “Telecommunications Fee”). The Telecommunications Fee for the contract year ending December 31, 2006 shall be $1.1 million.

(b) (i) The Telecommunications Fee will automatically escalate on the first anniversary date of this Agreement by the percentage increase in the Consumer Price Index for All Urban Consumers (“CPI-U”) as published by the U.S. Department of Labor, Bureau of Labor Statistics. The percentage increase in the CPI-U means the average percentage increase in the CPI-U over the first twelve (12) of the fifteen (15) months preceding the escalation date.

(ii) On the second anniversary of this Agreement and thereafter, the Telecommunications Fee shall be adjusted annually to reflect VCSC’s actual cost to provide the Telecommunications Services.

3

(c) At the end of each contract year, the scope of the Telecommunications Services and the related Telecommunications Fee are subject to review either at the request of VCSC or the Partnership Parties, in either case by providing 10 days written notice to the other party but in no event later than 60 days before the end of the applicable contract year, with such review to be completed no later than March 31 of the immediately following contract year, with any modification of the Telecommunications Fee other than as provided in paragraphs (a) and (b) above subject to the consent and approval of the Conflicts Committee.

(d) Any fees payable hereunder for periods less than a full contract year shall be prorated for the period services were provided based on the actual number of days elapsed and a year of 365 days.

Section 1.3 Payment of Fees.

(a) The fees to be paid pursuant to this Agreement shall be paid by the Partnership in equal monthly installments in arrears within 30 days of the end of the month.

(b) To the extent reasonably practicable, all third party invoices for Direct Charges shall be submitted to the Partnership Parties, for payment. For Direct Charges not paid directly by the Partnership Parties, if any, VCSC shall present Valero GP with an invoice within 10 days after the end of each calendar month which reflects an amount equal to all Direct Charges reimbursable to VCSC. The Partnership shall pay such sum within 30 days of the end of the applicable calendar month.

Section 1.4 Cancellation or Reduction of Services. The Partnership Parties may terminate or reduce the level of any Administrative or Telecommunications Service on 60 days’ prior written notice to VCSC. Upon such termination or reduction, the Administrative Services Fee or the Telecommunications Fee shall be reduced accordingly, whether on a temporary or a permanent basis, for such time as such service is reduced or terminated.

Section 1.5. Term. The provisions of this Article I will apply until this Agreement is terminated or amended in accordance with Section 2.1 or Section 2.13, respectively.

ARTICLE II

MISCELLANEOUS

Section 2.1 Termination.

(a) This Agreement shall terminate on December 30, 2010 (the “Initial Term”); provided that this Agreement shall automatically continue for successive two year terms after the Initial Term unless or until one year’s advance notice is given by VCSC to terminate this Agreement, in which case this Agreement shall terminate one year after such notice is delivered. Notwithstanding the foregoing, any Partnership Party (a) may terminate the provision of one or more Administrative Services, reduce the level of one or more Administrative Services in accordance with the provisions of Section 1.4 hereof or terminate or reduce the level of Telecommunications Services provided hereunder, and (b) shall have the

4

right at any time to terminate this Agreement by giving written notice to VCSC, and in such event this Agreement shall terminate one hundred and eighty (180) days from the date on which such notice is given.

(b) Notwithstanding Section 2.1(a), if a Change of Control (as defined below) of Valero GP Holdings, LLC (“Holdings”) or Valero GP occurs, this Agreement shall terminate. The following shall constitute a Change of Control:

(i) Holdings shall cease to own, directly or indirectly, 100% of each of Valero GP and the General Partner;

(ii) both (A) the Valero Energy Affiliates (as defined below) shall be in the aggregate the legal or beneficial owners (within the meaning of Rule 13d-3 under the Securities Exchange Act of 1934, as amended) of less than a majority of the combined voting power of the then total membership interests (including all securities which are convertible into membership interests) of Holdings, and (B) any Person (as defined below) or Group of Persons (as defined below) acting in concert as a partnership or other Group (a “Group of Persons”), other than one or more of the Valero Energy Affiliates, shall be the legal or beneficial owner (within the meaning of Rule 13d-3 under the Securities Exchange Act of 1934, as amended) of 20% or more of the combined voting power of the then total membership interests (including all securities which are convertible into membership interests) of Holdings, provided, that a “Group of Persons” shall not include the underwriter in any firm underwriting undertaken in connection with the initial public offering or any subsequent public offering of Holdings; or

(iii) occupation of a majority of the seats (other than vacant seats) on the Board of Directors (or Board of Managers) of Holdings by Persons who were neither (A) nominated by the board of directors of Holdings nor (B) appointed by directors, a majority of whom were so nominated.

(c) For purposes of Section 2.1 (b) the following terms shall mean:

“Associate” means, when used to indicate a relationship with any Person, (a) any corporation or organization which such Person is a director, officer or partner or is, directly or indirectly, the owner of 20% or more of any class of voting stock or other voting interest; (b) any trust or other estate in which such Person has at least a 20% beneficial interest or as to which such Person serves as trustee or in a similar fiduciary capacity; and (c) any relative or spouse of such Person, or any relative of such spouse, who has the same principal residence as such Person.

“Group” means a Person that with our through any of its Affiliates or Associates has any agreement, arrangement or understanding for the purpose of acquiring, holding, voting (except voting pursuant to a revocable proxy or consent given to such Person in response to a proxy or consent solicitation made to ten or more Persons), exercising investment power or disposing of any membership interests of Holdings with any other Person that beneficially owns, or whose Affiliates or Associates beneficially own, directly or indirectly, membership interests of Holdings.

5

“Person” means an individual or a corporation, limited liability company, partnership, joint venture, trust, unincorporated organization or other enterprise (including an employee benefit plan), association, government agency or political subdivision thereof or other entity.

“Valero Energy Affiliates” shall mean any and all Affiliates of Valero Energy.

Section 2.2 No Third Party Beneficiary. The provisions of this Agreement are enforceable solely by the parties to the Agreement and no limited partner, assignee or other person shall have the right, separate and apart from the parties hereto, to enforce any provisions of this Agreement or to compel an party to this Agreement to comply with the terms of this Agreement.

Section 2.3 No Fiduciary Duties The parties hereto shall not have any fiduciary obligations or duties to the other parties by reason of this Agreement. Subject to the Omnibus Agreement among Valero Energy (as successor to Ultramar Diamond Shamrock Corporation), Valero GP, the General Partner, the Partnership and Valero Logistics Operations, L.P., dated as of April 16, 2001, as such agreement may be amended from time to time, any party hereto may conduct any activity or business for its own profit whether or not such activity or business is in competition with any activity or business of the other party.

Section 2.4 Limited Warranty; Limitation of Liability

VCSC represents that it will provide or cause the services to be provided to the Partnership Parties with reasonable care and in accordance with all applicable laws, rules, and regulations, including without limitation those of the Federal Energy Regulatory Commission. EXCEPT AS SET FORTH IN THE IMMEDIATELY PRECEDING SENTENCE AND IN SECTION 1.1 (d), ALL PRODUCTS OBTAINED FOR THE PARTNERSHIP PARTIES ARE AS IS, WHERE IS, WITH ALL FAULTS AND VCSC MAKES NO (AND HEREBY DISCLAIMS AND NEGATES ANY AND ALL) REPRESENTATIONS AND WARRANTIES, EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE WITH RESPECT TO THE SERVICES RENDERED OR PRODUCTS OBTAINED FOR THE PARTNERSHIP PARTIES. FURTHERMORE, THE PARTNERSHIP PARTIES MAY NOT RELY UPON ANY REPRESENTATION OR WARRANTY, EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE MADE TO VCSC BY ANY PARTY (INCLUDING, AN AFFILIATE OF VCSC) PERFORMING SERVICES ON BEHALF OF VCSC HEREUNDER, UNLESS SUCH PARTY MAKES AN EXPRESS WARRANTY TO VALERO GP OR THE PARTNERSHIP PARTIES. HOWEVER, IN THE CASE OF SERVICES PROVIDED BY A THIRD PARTY FOR THE PARTNERSHIP PARTIES, IF THE THIRD PARTY PROVIDER OF SUCH SERVICES MAKES AN EXPRESS WARRANTY TO ANY OF THE PARTNERSHIP PARTIES, THE PARTNERSHIP PARTIES ARE ENTITLED TO CAUSE VCSC TO RELY ON AND TO ENFORCE SUCH WARRANTY.

6

IT IS EXPRESSLY UNDERSTOOD BY THE PARTNERSHIP PARTIES THAT VCSC AND ITS AFFILIATES SHALL HAVE NO LIABILITY FOR THE FAILURE OF THIRD PARTY PROVIDERS TO PERFORM ANY SERVICES HEREUNDER AND FURTHER THAT VCSC AND ITS AFFILIATES SHALL HAVE NO LIABILITY WHATSOEVER FOR THE SERVICES PROVIDED BY ANY SUCH THIRD PARTY UNLESS IN EITHER EVENT SUCH SERVICES ARE PROVIDED IN A MANNER WHICH WOULD EVIDENCE GROSS NEGLIGENCE OR INTENTIONAL MISCONDUCT ON THE PART OF VCSC OR ITS AFFILIATES BUT VCSC SHALL, ON BEHALF OF THE PARTNERSHIP PARTIES, PURSUE ALL RIGHTS AND REMEDIES UNDER ANY SUCH THIRD PARTY CONTRACT. THE PARTNERSHIP PARTIES AGREE THAT THE REMUNERATION PAID TO VCSC HEREUNDER FOR THE SERVICES TO BE PERFORMED REFLECT THIS LIMITATION OF LIABILITY AND DISCLAIMER OF WARRANTIES. IN NO EVENT SHALL VCSC BE LIABLE TO THE PARTNERSHIP PARTIES OR ANY OTHER PERSON FOR ANY INDIRECT, SPECIAL, OR CONSEQUENTIAL DAMAGES RESULTING FROM ANY ERROR IN THE PERFORMANCE OF SERVICES OR FROM THE BREACH OF THIS AGREEMENT, REGARDLESS OF THE FAULT OF VCSC, ANY VCSC AFFILIATE, OR ANY THIRD PARTY PROVIDER OR WHETHER VCSC, ANY VCSC AFFILIATE, OR THE THIRD PARTY PROVIDER ARE WHOLLY, CONCURRENTLY, PARTIALLY, OR SOLELY NEGLIGENT. TO THE EXTENT ANY THIRD PARTY PROVIDER HAS LIMITED ITS LIABILITY TO VCSC OR ITS AFFILIATE FOR SERVICES UNDER AN OUTSOURCING OR OTHER AGREEMENT, THE PARTNERSHIP PARTIES AGREE TO BE BOUND BY SUCH LIMITATION OF LIABILITY FOR ANY PRODUCT OR SERVICE PROVIDED TO THE PARTNERSHIP PARTIES BY SUCH THIRD PARTY PROVIDER UNDER VCSC’S OR SUCH AFFILIATE’S AGREEMENT.

Section 2.5 Force Majeure. If any party to this Agreement is rendered unable by force majeure to carry out its obligations under this Agreement, other than a party’s obligation to make payments as provided for herein, that party shall give the other parties prompt written notice of the force majeure with reasonably full particulars concerning it. Thereupon, the obligations of the party giving the notice, insofar as they are affected by the force majeure, shall be suspended during, but no longer than the continuance of, the force majeure. The affected party shall use all reasonable diligence to remove or remedy the force majeure situation as quickly as practicable.

The requirement that any force majeure situation be removed or remedied with all reasonable diligence shall not require the settlement of strikes, lockouts or other labour difficulty by the party involved, contrary to its wishes. Rather, all such difficulties may be handled entirely within the discretion of the party concerned.

The term “force majeure” means any one or more of: (a) an act of God, (b) a strike, lockout, labour difficulty or other industrial disturbance, (c) an act of a public enemy, war, blockade, insurrection or public riot, (d) lightning, fire, storm, flood or explosion, (e) governmental action, delay, restraint or inaction, (f) judicial order or injunction, (g) material shortage or unavailability of equipment, or (h) any other cause or event, whether of the kind specifically enumerated above or otherwise, which is not reasonably within the control of the party claiming suspension.

7

Section 2.6 Further Assurances. In connection with this Agreement and all transactions contemplated by this Agreement, each signatory party hereto agrees to execute and deliver such additional documents and instruments as may be required for a party to provide the services hereunder and to perform such other additional acts as may be necessary or appropriate to effectuate, carry out, and perform all of the terms and provisions of this Agreement.

Section 2.7 Time of the Essence. Time is of the essence in this Agreement.

Section 2.8 Notices. Any notice, request, demand, direction or other communication required or permitted to be given or made under this Agreement to a party shall be in writing and may be given by hand delivery, postage prepaid first-class mail delivery, delivery by a reputable international courier service guaranteeing next business day delivery or by facsimile (if confirmed by one of the foregoing methods) to such party at its address noted below:

(a) in the case of VCSC, to:

Valero Corporate Services Company

One Valero Way

San Antonio, Texas 78249

Attention: Legal Department

Telecopy: (210)  ###-###-####

(b) in the case of the General Partner and Valero GP, to:

Valero GP, LLC

One Valero Way

San Antonio, Texas 78249

Attention: Legal Department

Telecopy: (210)  ###-###-####

or at such other address of which notice may have been given by such party in accordance with the provisions of this Section.

Section 2.9 Counterparts. This Agreement may be executed in several counterparts, no one of which needs to be executed by all of the parties. Such counterpart, including a facsimile transmission of this Agreement, shall be deemed to be an original and shall have the same force and effect as an original. All counterparts together shall constitute but one and the same instrument.

Section 2.10 Applicable Law. The provisions of this Agreement shall be construed in accordance with the laws of the State of Texas, excluding any conflicts of law rule or principle that might refer the construction or interpretation hereof to the laws of another jurisdiction.

Section 2.11 Binding Effect; Assignment. Except for the ability of VCSC to cause one or more of the Administrative Services to be performed by a third party provider or an Affiliate of VCSC, no party shall have the right to assign its rights or obligations under this Agreement without the consent of the other parties.

8

Section 2.12 Invalidity of Provisions. In the event that one or more of the provisions contained in this Agreement shall be invalid, illegal or unenforceable in any respect under any applicable law, the validity, legality or enforceability of the remaining provisions hereof shall not be affected or impaired thereby.

Section 2.13 Modification; Amendment. This Agreement may be amended or modified from time to time only by a written amendment signed by all parties hereto; provided however, that the Partnership Parties may not, without the prior approval of the Conflicts Committee, agree to any amendment or modification to this Agreement that, in the reasonable discretion of the General Partner, will adversely affect the holders of common units of the Partnership.

Section 2.14 Entire Agreement. This Agreement constitutes the whole and entire agreement between the parties hereto and supersedes any prior agreement, undertaking, declarations, commitments or representations, verbal or oral, in respect of the subject matter hereof.

9

IN WITNESS WHEREOF, the parties hereto have executed this Agreement with effect as of the date first above written.

SIGNATURE PAGE TO THIRD AMENDED AND RESTATED SERVICES AGREEMENT

10

EXHIBIT A

Administrative Services provided to the Partnership Parties:

IS Support

Corporate Tax

Ad Valorem Tax

Human Resources (benefits, compensation, employment, payroll, corporate HR support)

PR/Community Relations

Governmental Affairs

Graphic Services

Risk Control & Analysis

Risk Management

Corporate Records

Corporate Travel/Aviation^(a)

Office Services^(b)

Facility Services^(b)

Corporate Services Department^(b)

Security Services^(b)

Other Administrative Services as the parties may agree.

In providing the foregoing services, VCSC shall be acting on behalf of and as agent for the Partnership Parties.

Notes:

(a) Aviation Services may be documented under a time-share arrangement, in which case, the Administrative Services Fee will be reduced by $70,250.

(b) Upon the Commencement Date, as that term is defined in that certain Office Lease Agreement between Valero Corporate Services Company and Valero Logistics Operations, L.P., dated as of January 1, 2006 (the “Lease Agreement”), the Administrative Services Fee shall be reduced by $130,000 to account for the assumption of Office Services, Facility Services, Corporate Services and Security that will be provided to the Partnership Parties pursuant to the Lease Agreement.

A-1