ADMINISTRATION AGREEMENT BETWEEN VALERO GP HOLDINGS, LLC AND VALERO GP, LLC DATED AS OF July 19, 2006

Exhibit 10.04

ADMINISTRATION AGREEMENT

BETWEEN

VALERO GP HOLDINGS, LLC

AND

VALERO GP, LLC

DATED AS OF July 19, 2006

ADMINISTRATION AGREEMENT

This ADMINISTRATION AGREEMENT (this “Agreement”) is entered into as of July 19, 2006 and effective as of Effective Date, as defined below, between VALERO GP HOLDINGS, LLC, a Delaware limited liability company (“Holdings”), and VALERO GP, LLC, a Delaware limited liability company (“Valero GP”).

RECITALS

WHEREAS, management of Holdings has determined that certain executive management, accounting, legal, cash management, corporate finance and other administrative services required by Holdings should be performed by Valero GP in exchange for an administrative services fee;

WHEREAS, on March 10, 2006, upon recommendation by management of Valero GP and the Conflicts Committee of the Board of Directors of Valero GP (the “Conflicts Committee”), the Board of Directors of Valero GP approved the terms of this Agreement;

WHEREAS, Valero GP has agreed to provide certain administrative services under this Agreement to Holdings; and

NOW, THEREFORE, for and in consideration of the mutual covenants contained in this Agreement, the parties hereto hereby agree as follows:

ARTICLE I
DEFINITIONS

Section 1.1            Definitions.   The following definitions shall be for all purposes, unless otherwise clearly indicated to the contrary, applied to the terms used in this Agreement.

(a)           “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 Valero GP, the term “Affiliate” shall exclude Holdings.

(b)           “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.

(c)           “Effective Date” means the closing date of the initial public offering of Holdings.

(d)           “force majeure” means any one or more of: (a) an act of God, (b) a strike, lockout, labor 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..

(e)           “Group” means a Person that with or 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 in Holdings with any other Person that beneficially owns, or whose Affiliates or Associates beneficially own, directly or indirectly, membership interests in Holdings.

(f)            “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.

(g)           “Valero Energy Affiliates” shall mean any and all Affiliates of Valero Energy Corporation.

ARTICLE II
PROVISION OF SERVICES

Section 2.1                Provision of Administrative Services by Valero GP.

(a)           Administrative Services.  Valero GP or any Affiliate or designee of Valero GP shall provide to Holdings non-exclusive executive management, accounting, legal, cash management, corporate finance and other administrative services, and such other services as Valero GP and Holdings may from time to time agree (the “Administrative Services”).

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

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

all third party expenses directly related to Holdings, including, but not limited to, public company costs, outside legal fees, outside accounting fees, fees and expenses of directors, external advisors and consultants, and insurance costs, including but not limited to, directors and officers.

2

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

Section 2.2            Fees for Administrative Services.

(a)           Commencing on the Effective Date of this Agreement, and for each contract year thereafter, Holdings shall pay to Valero GP an annual fee (the “Administrative Services Fee”).  The Administrative Services Fee shall be $500,000 per year, subject to adjustment as provided in Section 2.2(b).

(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 GP’s general annual merit increase percentage for the just completed contract year.

(c)           Valero GP, with the approval and consent of the Conflicts Committee, may agree to further modifications in the Administrative Services Fee in connection with changed levels of Administrative Services provided to Holdings due to modifications of Holdings’ operations through acquisitions or otherwise.

(d)           The parties hereto acknowledge that the Administrative Services Fee is intended to reflect Valero GP’s actual costs to provide the Administrative Services.  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 Valero GP or Holdings, 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 Sections 2.2 (b) and 2.4, 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 for which services were provided based on the actual number of days elapsed and a year of 365 days.

Section 2.3                Payment of Fees.

(a)           The fees to be paid pursuant to this Agreement shall be paid by Holdings 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 Holdings for payment.  For Direct Charges not paid directly by Holdings, if any, Valero GP shall present Holdings with an invoice within 10 days after the end of each calendar month that reflects an amount equal to all Direct Charges reimbursable to Valero GP.  Holdings shall pay such sum within 30 days of the end of the applicable calendar month.

Section 2.4            Cancellation or Reduction of Services.   Holdings may terminate or reduce the level of any Administrative Service on 60 days’ prior written notice to Valero GP.  Upon such termination or reduction, the Administrative Services Fee shall be reduced

3

accordingly, whether on a temporary or a permanent basis, for such time as such service is reduced or terminated.

Section 2.5            Term.   The provisions of this Article II will apply until this Agreement is terminated or amended in accordance with Section 3.1 or Section 3.12, respectively.

ARTICLE III
MISCELLANEOUS

Section 3.1            Termination/Change of Control.

(a)           This Agreement shall terminate on December 31, 2011 (the “Initial Term”); provided that this Agreement shall automatically continue for successive two-year terms after the Initial Term unless or until six months’ advance notice is given by Valero GP to terminate this Agreement, in which case this Agreement shall terminate six months after such notice is delivered.  Notwithstanding the foregoing, Holdings (i) may terminate the provision of one or more Administrative Services or reduce the level of one or more Administrative Services, in each case in accordance with the provisions of Section 2.4 hereof and (ii) shall have the right at any time to terminate this Agreement by giving written notice to Valero GP, and in such event this Agreement shall terminate six months from the date on which such notice is given.

(b)           Notwithstanding Section 3.1(a), if a Change of Control of 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 Riverwalk Logistics, L.P., a Delaware limited partnership (“Riverwalk”);

(ii)           both (A) the Valero Energy Affiliates 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 or Group of Persons 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 more than 20% 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.

4

Section 3.2                No Third Party Beneficiary.  The provisions of this Agreement are enforceable solely by the parties to the Agreement and no limited partner, assignee, member 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 3.3                No Fiduciary Duties.  Neither party hereto shall have any fiduciary obligations or duties to the other party by reason of this Agreement.  Subject to the (i) Omnibus Agreement among Valero Energy Corporation (as successor to Ultramar Diamond Shamrock Corporation), Valero GP, Riverwalk, Valero L.P. and Valero Logistics Operations, L.P., dated as of April 16, 2001, as such agreement may be amended from time to time, and (ii) Non-Compete Agreement among Holdings, Valero GP, Riverwalk and Valero L.P., dated as of [                   ], 2006, 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 3.4                Limited Warranty; Limitation of Liability

Valero GP represents that it will provide or cause the services to be provided to Holdings 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 2.1 (d), ALL PRODUCTS OBTAINED FOR HOLDINGS ARE AS IS, WHERE IS, WITH ALL FAULTS AND VALERO GP 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 HOLDINGS.  FURTHERMORE, HOLDINGS MAY NOT RELY UPON ANY REPRESENTATION OR WARRANTY, EXPRESS OR IMPLIED, INCLUDING THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE MADE TO VALERO GP BY ANY PARTY (INCLUDING, AN AFFILIATE OR DESIGNEE OF VALERO GP) PERFORMING SERVICES ON BEHALF OF VALERO GP HEREUNDER, UNLESS SUCH PARTY MAKES AN EXPRESS WARRANTY TO HOLDINGS.  HOWEVER, IN THE CASE OF SERVICES PROVIDED BY A THIRD PARTY FOR HOLDINGS, IF THE THIRD PARTY PROVIDER OF SUCH SERVICES MAKES AN EXPRESS WARRANTY TO HOLDINGS, HOLDINGS IS ENTITLED TO CAUSE VALERO GP TO RELY ON AND TO ENFORCE SUCH WARRANTY.

IT IS EXPRESSLY UNDERSTOOD BY HOLDINGS THAT VALERO GP AND ITS AFFILIATES AND DESIGNEES SHALL HAVE NO LIABILITY FOR THE FAILURE OF THIRD PARTY PROVIDERS TO PERFORM ANY SERVICES HEREUNDER AND FURTHER THAT VALERO GP AND ITS AFFILIATES AND DESIGNEES 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 VALERO GP OR ITS AFFILIATES OR DESIGNEES BUT VALERO GP SHALL, ON BEHALF OF HOLDINGS, PURSUE ALL RIGHTS AND REMEDIES UNDER

5

ANY SUCH THIRD PARTY CONTRACT.  HOLDINGS AGREES THAT THE REMUNERATION PAID TO ALERO GP HEREUNDER FOR THE SERVICES TO BE PERFORMED REFLECT THIS LIMITATION OF LIABILITY AND DISCLAIMER OF WARRANTIES.  IN NO EVENT SHALL VALERO GP BE LIABLE TO HOLDINGS 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 VALERO GP, ANY VALERO GP AFFILIATE OR DESIGNEE, OR ANY THIRD PARTY PROVIDER OR WHETHER VALERO GP, ANY VALERO GP AFFILIATE OR DESIGNEE, OR THE THIRD PARTY PROVIDER ARE WHOLLY, CONCURRENTLY, PARTIALLY, OR SOLELY NEGLIGENT.  TO THE EXTENT ANY THIRD PARTY PROVIDER HAS LIMITED ITS LIABILITY TO VALERO GP OR ITS AFFILIATE OR DESIGNEE FOR SERVICES UNDER AN OUTSOURCING OR OTHER AGREEMENT, HOLDINGS AGREES TO BE BOUND BY SUCH LIMITATION OF LIABILITY FOR ANY PRODUCT OR SERVICE PROVIDED TO HOLDINGS BY SUCH THIRD PARTY PROVIDER UNDER VALERO GP’S OR SUCH AFFILIATE’S OR DESIGNEE’S AGREEMENT.

Section 3.5                Force Majeure.  If either 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 party 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 labor difficulty by the party involved, contrary to its wishes. Rather, all such difficulties may be handled entirely within the discretion of the party concerned.

Section 3.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 3.7                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 Valero GP, to:

Valero GP, LLC

6

One Valero Way
San Antonio, Texas 78249
Attention:  Legal Department

Telecopy: (210) 345-4861

(b)                                 in the case of Holdings, to:

Valero GP Holdings, LLC
One Valero Way
San Antonio, Texas 78249
Attention: Legal Department
Telecopy: (210) 345-xxxx

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

Section 3.8            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 3.9            Applicable Law.  he 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 3.10         Binding Effect; Assignment.  Except for the ability of Valero GP to cause one or more of the Administrative Services to be performed by a third party provider or an Affiliate of Valero GP, no party shall have the right to assign its rights or obligations under this Agreement (by operation of law or otherwise) without the consent of the other parties.

Section 3.11         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 3.12         Modification; Amendment.  This Agreement may be amended or modified from time to time only by a written amendment signed by both parties hereto; provided however, that Valero GP 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 Valero GP, will adversely affect the holders of common units of the Partnership.

Section 3.13         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.

7

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