Exhibit 4.01

Form of
Certificate Evidencing Units

Representing Interests in

Valero GP Holdings, LLC

No. [       ] [       ] Units

      In accordance with Section 4.1 of the Second Amended and Restated Limited Liability Company Agreement of Valero GP Holdings, LLC, as amended, supplemented or restated from time to time (the “Company Agreement”), Valero GP Holdings, LLC, a Delaware limited liability company (the “Company”), hereby certifies that [                    ] (the “Holder”) is the registered owner of [                    ] Units representing Interests in the Company (the “Units”) transferable on the books of the Company, in person or by duly authorized attorney, upon surrender of this Certificate properly endorsed. The rights, preferences and limitations of the Units are set forth in, and this Certificate and the Units represented hereby are issued and shall in all respects be subject to the terms and provisions of, the Company Agreement. Copies of the Company Agreement are on file at, and will be furnished without charge on delivery of written request to the Company at, the principal office of the Company located at One Valero Way, San Antonio, Texas 78249 or such other address as may be specified by notice under the Company Agreement. Capitalized terms used herein but not defined shall have the meanings given them in the Company Agreement.

The Holder, by accepting this Certificate, is deemed to have (i) requested admission as, and agreed to become, a Member and to have agreed to comply with and be bound by and to have executed the Company Agreement, (ii) represented and warranted that the Holder has all right, power and authority and, if an individual, the capacity necessary to enter into the Company Agreement, (iii) granted the powers of attorney provided for in the Company Agreement and (iv) made the waivers and given the consents and approvals contained in the Company Agreement.

This Certificate shall be governed by, and construed in accordance with, the laws of the State of Delaware, without regard to principles of conflict of laws thereof.

This Certificate shall not be valid for any purpose unless it has been countersigned and registered by the Transfer Agent and Registrar.

Valero GP Holdings, LLC	DATED:
By:	COUNTERSIGNED AND REGISTERED:
President and Chief Executive Officer
By:
Vice President, General Counsel and Secretary	TRANSFER AGENT AND REGISTRAR,
	By:

Reverse of Certificate

THIS CERTIFICATE ALSO EVIDENCES AND ENTITLES THE HOLDER HEREOF TO CERTAIN RIGHTS, SUBJECT TO ADJUSTMENT, AS SET FORTH IN A RIGHTS AGREEMENT BETWEEN VALERO GP HOLDINGS, LLC AND COMPUTERSHARE INVESTOR SERVICES, LLC DATED AS OF JULY 19, 2006, AS MAY BE AMENDED FROM TIME TO TIME (THE “RIGHTS AGREEMENT”), THE TERMS OF WHICH ARE HEREBY INCORPORATED HEREIN BY REFERENCE AND A COPY OF WHICH IS ON FILE AT THE PRINCIPAL EXECUTIVE OFFICES OF VALERO GP HOLDINGS, LLC. UNDER CERTAIN CIRCUMSTANCES, AS SET FORTH IN THE RIGHTS AGREEMENT, SUCH RIGHTS WILL BE EVIDENCED BY SEPARATE CERTIFICATES AND WILL NO LONGER BE EVIDENCED BY THIS CERTIFICATE. VALERO GP HOLDINGS, LLC WILL MAIL TO THE HOLDER OF THIS CERTIFICATE A COPY OF THE RIGHTS AGREEMENT WITHOUT CHARGE AFTER RECEIPT OF A WRITTEN REQUEST THEREFOR. UNDER CERTAIN CIRCUMSTANCES, AS SET FORTH IN THE RIGHTS AGREEMENT, RIGHTS ISSUED TO, OR HELD BY, ANY PERSON WHO BECOME AN ACQUIRING PERSON (AS DEFINED IN THE RIGHTS AGREEMENT) AND CERTAIN TRANSFEREES THEREOF WILL BECOME NULL AND VOID.

      The following abbreviations, when used in the inscription on the face of this Certificate, shall be construed as follows according to applicable laws or regulations:

TEN COM —	as tenants in common	UNIF GIFT/TRANSFERS MIN ACT
TEN ENT —	as tenants by the entireties	_________ Custodian _________________
		(Cust)                          (Minor)
JT TEN —	as joint tenants with right of survivorship and not as tenants in common	under Uniform Gifts/Transfers to CD Minors Act ____________________ (State)

      Additional abbreviations may also be used though not in the above list.

ASSIGNMENT OF UNITS

IN

VALERO GP HOLDINGS, LLC

FOR VALUE RECEIVED,                      HEREBY ASSIGNS, CONVEYS, SELLS AND TRANSFERS UNTO

(Please print or typewrite name and address of Assignee) (Please insert Social Security or other identifying number of Assignee)

Units representing Interests evidenced by this Certificate, subject to the Company Agreement, and does hereby irrevocably constitute and
 
appoint                                                     as its attorney-in-fact with full power of substitution to transfer the same on the books of Valero GP Holdings, LLC.

Dated:                                                                                     20	NOTE: The signature to any endorsement hereon must correspond with the name as written upon the face of this Certificate in every particular, without alteration, enlargement or change.
SIGNATURE(S) MUST BE GUARANTEED BY A MEMBER FIRM OF THE NATIONAL ASSOCIATION OF SECURITIES DEALERS, INC. OR BY A COMMERCIAL BANK OR TRUST COMPANY SIGNATURE(S) GUARANTEED	(Signature)
	(Signature)

No transfer of the Units evidenced hereby will be registered on the books of the Company, unless the Certificate evidencing the Units to be transferred is surrendered for registration of transfer.