AMENDED AND RESTATED

Exhibit 10.1

AMENDED AND RESTATED

SERVICES AGREEMENT

AMONG

DIAMOND SHAMROCK REFINING AND MARKETING COMPANY

VALERO L.P.

VALERO LOGISTICS OPERATIONS, L.P.

RIVERWALK LOGISTICS, L.P.

AND

VALERO GP, L.L.C.

DATED AS OF APRIL 1, 2004

AMENDED AND RESTATED SERVICES AGREEMENT

This AMENDED AND RESTATED SERVICES AGREEMENT (this “Agreement”) is entered into effective as of April 1, 2004 (the “Effective Date”) by and among DIAMOND SHAMROCK REFINING AND MARKETING COMPANY, a Delaware corporation (“DSRMC”) and an indirect wholly owned subsidiary of Valero Energy Corporation (“Valero Energy”), VALERO L.P. (f/k/a Shamrock Logistics, L.P.), a publicly traded Delaware limited partnership (the “Partnership”), VALERO LOGISTICS OPERATIONS, L.P. (f/k/a Shamrock Logistics Operations) (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”) (f/k/a Shamrock Logistics GP, LLC).

RECITALS

WHEREAS, Valero GP, a wholly owned subsidiary of DSRMC and an indirect wholly owned subsidiary of Valero Energy, is the general partner of the General Partner; and

WHEREAS, the General Partner is the general partner of the Partnership; and

WHEREAS, all management powers over the business and affairs of the Partnership are exclusively vested in the General Partner and the General Partner is required to conduct, direct and exercise full control over all activities of the Partnership, including, among other things, providing various general and administrative resources and services; and

WHEREAS, the parties entered into a Services Agreement effective July 1, 2000 pursuant to which DSRMC agreed to provide (i) specified corporate, general and administrative services to the General Partner for an annual administrative fee of $5.2 million, subject to adjustment as provided in the Services Agreement and (ii) other specified services necessary to operate and maintain the assets and operations of the Partnership, with such other services being reimbursable to DSRMC; and

WHEREAS, the Services Agreement provides that the General Partner, with the approval and consent of the conflicts committee (the “Conflicts Committee”) of Valero GP, may (i) agree on behalf of the Partnership to increases in the Administrative Services Fee (as such term is defined in the Services Agreement) in connection with expansions of the Partnership’s operations through acquisition or construction of new assets or businesses, and (ii) amend or modify the Services Agreement; and

WHEREAS, on March 4, 2004, the Conflicts Committee approved a new Administrative Services Fee and the terms of this Agreement;

WHEREAS, the parties desire to amend and restate the Services Agreement as set forth herein to reflect the significant changes that have occurred in the business and operations of the Partnership since the effective date of the Services Agreement and the initial public offering of the Partnership on April 16, 2001; and

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

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

ARTICLE I

PROVISION OF SERVICES

Section 1.1 Provision of Services.

(a) General and Administrative Services. DSRMC or any Affiliate or designee of DSRMC shall provide non-exclusive management, employee-related and other related services to the Partnership Parties through Valero GP or any Affiliate, which shall include, but shall not be limited to, services related to acquisitions to be made by the Partnership Parties, cash management, review of significant financial opportunities and operating, accounting, legal, engineering, commercial, human resources, information technology and such other management, employee-related and other general and administrative services as set forth on Exhibit A hereto and as DSRMC 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 DSRMC, the term “Affiliate” shall exclude Valero GP, the General Partner, the Partnership and the Operating Partnership.

(b) Additional Services. DSRMC or any Affiliate 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.

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

(i) all salaries, wages and benefits costs related to personnel dedicated to the Partnership Parties, including, but not limited to, variable and incentive compensation, FICA, vacation pay, sick pay, life insurance, disability insurance, workers compensation, 401(k) matching contribution costs, defined benefit pension costs and post retirement health and medical costs. For purposes of this subsection (c)(i), personnel shall be considered “dedicated to the Partnership Parties” if such person dedicates 75% or more of his or her time to the Partnership Parties; and

3

(ii) 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 shall be substantially identical to those provided to other subsidiaries and Affiliates of DSRMC.

Section 1.2 Fees.

(a) Commencing on the Effective Date of this Agreement and ending on December 31, 2004, and for each fiscal year of the Partnership thereafter, the Partnership shall pay to DSRMC an annual fee (the “Administrative Services Fee”). The Administrative Services Fee for the fiscal year ended December 31, 2004 shall be $900,000, for the fiscal year ended December 31, 2005 shall be $2,400,000, and thereafter such fee shall increase by $1.2 million in each of the three next following fiscal years, resulting in an Administrative Services Fee of $6.0 million for the fiscal year ended December 31, 2008 and the fiscal years following, subject to adjustment as provided in paragraph (b) below.

(b) On the last day of each fiscal year starting with the fiscal year ending December 31, 2004, and prior to the beginning of the next fiscal 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 fiscal year.

(c) The General Partner, with the approval and consent of the Conflicts Committee, may agree on behalf of the Partnership to further increases in the Administrative Services Fee in connection with increased 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 fiscal year, the scope of the Administrative Services and the related Administrative Services Fee are subject to review either at the request of DSRMC 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 fiscal year, with such review to be completed no later than January 31 of the immediately following fiscal year, with any increase of the Administrative Services Fee other than as provided in paragraph (a) above subject to the consent and approval of the Conflicts Committee.

(e) Any fees payable hereunder for periods less than a full fiscal year shall be prorated for the period services were provided based on the actual number of days elapsed and a year of 365 days. The Administrative Services Fee set forth in Section 1.2 (a) above applicable to the fiscal year ended December 31, 2004 has already been prorated and no further proration for the fiscal year ended December 31, 2004 shall apply.

4

Section 1.3 Payment of Fees.

(a) The fees to be paid pursuant to Section 1.2 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 due DSRMC from the Partnership, if any, DSRMC 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 DSRMC. 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 Service on 60 days’ prior written notice to DSRMC. Upon such termination or reduction, the Administrative Services Fee shall be reduced accordingly, whether on a temporary or a permanent basis, for such time as such Administrative Service is reduced or terminated.

Section 1.5 Term. The provisions of this Article I will apply in respect of Administrative Services 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. This Agreement shall terminate on December 31, 2009 (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 DSRMC 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 or reduce the level of one or more Administrative Services in accordance with the provisions of Section 1.4 hereof, and (b) shall have the right at any time to terminate this Agreement by giving written notice to DSRMC, and in such event this Agreement shall terminate one hundred and eighty (180) days from the date on which such notice is given.

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, any party hereto may conduct any activity or business for its own profit

5

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 DSRMC represents that it will provide or cause the Administrative 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 DSRMC 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 DSRMC BY ANY PARTY (INCLUDING, AN AFFILIATE OF DSRMC) PERFORMING SERVICES ON BEHALF OF DSRMC 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 DSRMC TO RELY ON AND TO ENFORCE SUCH WARRANTY.

IT IS EXPRESSLY UNDERSTOOD BY THE PARTNERSHIP PARTIES THAT DSRMC AND ITS AFFILIATES SHALL HAVE NO LIABILITY FOR THE FAILURE OF THIRD PARTY PROVIDERS TO PERFORM ANY SERVICES HEREUNDER AND FURTHER THAT DSRMC 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 DSRMC OR ITS AFFILIATES BUT DSRMC 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 DSRMC HEREUNDER FOR THE SERVICES TO BE PERFORMED REFLECT THIS LIMITATION OF LIABILITY AND DISCLAIMER OF WARRANTIES. IN NO EVENT SHALL DSRMC 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 DSRMC, ANY DSRMC AFFILIATE, OR ANY THIRD PARTY PROVIDER OR WHETHER DSRMC, ANY DSRMC 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 DSRMC OR ITS AFFILIATE FOR SERVICES UNDER AN OUTSOURCING

6

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 DSRMC’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 Valero GP’s or the General Partner’s obligation to make payments to DSRMC 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.

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 DSRMC or its Affiliates to provide the Administrative 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:

Diamond Shamrock Refining and Marketing Company

6000 North Loop 1604 West

San Antonio, Texas 78249

Attention: Legal Department

Telecopy: (210) 370-5889

7

Valero GP, LLC

6000 North Loop 1604 West

San Antonio, Texas 78249

Attention: President

Telecopy: (210) 370-

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 DSRMC to cause one or more of the Administrative Services to be performed by a third party provider or an Affiliate, no party shall have the right to assign its rights or obligations under this Agreement without the consent of the other parties.

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.

8

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

SIGNATURE PAGE TO AMENDED AND RESTATED ADMINISTRATIVE SERVICES AGREEMENT

9

EXHIBIT A

Administrative Services provided to the Partnership Parties:

Ad Valorem Tax Services (note: ad valorem taxes are Direct Charges)

Controller

External Reporting

Corporate Tax

Accounting Governance

Non-Hydrocarbons Operations Accounting

Corporate Aviation and Travel Services

Corporate Communications and Public Relations

Corporate Development

Data Processing and Information Technology Services

Executive Oversight

Financial Accounting and Reporting

Foreign Trade Zone Reporting and Accounting

Governmental Affairs

Group Accounting

Health, Safety & Environmental Services

Human Resources Services

Benefit Accounting

Benefit Plan Administration

Retirement Plan Administration

401(k) Savings Plan Administration

Payroll Services

Training Services

Internal Audit

Legal

General Litigation Support

General Corporate

General Commercial

Labor & Employment

Tariff Maintenance

Environmental and Regulatory

Office Services

Mail Center/Mail Services

Health Club

Office Space including building maintenance

Purchasing/Fleet Management

Records Management

Real Estate Management

Risk and Claims Management Services (note: insurance premiums are Direct Charges)

Security Services

Shareholder and Investor Relations

Treasury & Banking

Finance Services

Cash Management

Credit Services

A-1

Exhibit A (continued)

Note: Salaries, wages and benefits for some personnel providing some of the Administrative Services listed above will be charged directly to the Partnership Parties in accordance with Section 1.1(c) of the Agreement.

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

A-2