EXHIBIT 5.01

December    , 2006

Valero GP Holdings, LLC
One Valero Way
San Antonio, Texas 78249

Gentlemen:

        We have acted as special counsel to Valero GP Holdings, LLC, a Delaware limited liability company (the "Company"), Sigmor Corporation, a Delaware corporation ("Sigmor"), and Diamond Shamrock Refining and Marketing Company, a Delaware corporation ("DSRMC" and together with Sigmor, the "Selling Unitholders") in connection with the registration under the Securities Act of 1933, as amended (the "Securities Act"), of the offering and sale by the Selling Unitholders of up to an aggregate of 25,250,000 units representing limited liability company interests in the Company (the "Units").

        As the basis for the opinion hereinafter expressed, we have examined such statutes, including the Delaware Limited Liability Company Act (the "Delaware LLC Act"), regulations, corporate records and documents, certificates of corporate and public officials, and other instruments and documents as we have deemed necessary or advisable for the purposes of this opinion. In making our examination, we have assumed that all signatures on documents examined by us are genuine, the authenticity of all documents submitted to us as originals and the conformity with the original documents of all documents submitted to us as certified, conformed or photostatic copies.

        Based on the foregoing and on such legal considerations as we deem relevant, we are of the opinion that the Units, when issued and delivered on behalf of the Selling Unitholders against payment therefore as described in the Company's Registration Statement on Form S-1 (Commission File No. 333-        ), as amended, relating to the Units (the "Registration Statement"), will be duly authorized, validly issued, fully paid and nonassessable.

        We hereby consent to the reference to us under the heading "Validity of the Units" in the prospectus forming a part of the Registration Statement and to the filing of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Securities and Exchange Commission issued thereunder.

        This opinion speaks as of its date, and we undertake no, and hereby disclaim any, duty to advise as to changes of fact or law coming to our attention after the delivery hereof on such date.

Austin      Beijing      Dallas      Houston      London      Los Angeles      New York       The Woodlands      Washington, DC

The opinion expressed herein is limited exclusively to the Delaware LLC Act and the laws of the state of Delaware, and we are expressing no opinion as to the effect of the laws of any other jurisdiction.

Very truly yours,

2