Exhibit 5.1

November 4, 2013

CST Brands, Inc.

One Valero Way

Building D, Suite 200

San Antonio, TX 78249

Ladies and Gentlemen:

We have acted as special counsel to CST Brands, Inc., a Delaware corporation (the “Company”), in connection with the Company’s Registration Statement on Form S-1 (the “Registration Statement” which term does not include any other document or agreement whether or not specifically referred to therein or attached as an exhibit or schedule thereto), initially filed by the Company with the U.S. Securities and Exchange Commission (the “SEC”) on September 13, 2013, as amended on October 16, 2013 relating to the registration under the U.S. Securities Act of 1933, as amended (the “Securities Act”), of up to 13,112,564 shares of common stock, par value $0.01 per share, of the Company (or up to 15,079,448 shares if the underwriters exercise in full their option to purchase additional shares) (the “Shares”) to be sold by Valero Energy Corporation, a Delaware corporation (“Valero”), in the manner described in the Registration Statement.

For the purposes of giving the opinion contained herein, we have examined the Registration Statement, the form of Exchange Agreement among Valero, Citicorp North America, Inc. (“Citicorp”), and, for limited purposes, the Company (the “Exchange Agreement”) and the form of Underwriting Agreement among the Company, Valero, and the underwriters named therein (the “Underwriting Agreement”). We have also examined the originals, or duplicates or certified or conformed copies, of such corporate records, agreements, documents and other instruments, including the certificate of incorporation and bylaws of the Company, and have made such other investigations as we have deemed relevant and necessary in connection with the opinions set forth below. As to questions of fact material to this opinion, we have relied, with your approval, upon oral and written representations of officers and representatives of the Company, Valero, Citicorp and the underwriters and certificates or comparable documents of public officials and of officers and representatives of the Company, Valero, Citicorp and the underwriters.

In making such examination and rendering the opinions set forth below, we have assumed without verification the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the authenticity of the originals of such documents submitted to us as certified copies, the conformity to originals of all documents submitted to us as copies, the authenticity of the originals of such documents, that all documents submitted to us as certified copies are true and correct copies of such originals and the legal capacity of all individuals executing any of the foregoing documents.

CST Brands, Inc.

November 4, 2013

Page 2

In rendering the opinion set forth below, we have also assumed that the Shares were duly authenticated by the transfer agent and registrar for the Shares and that the certificates, if any, evidencing the Shares to be issued will be manually signed by one of the authorized officers of the transfer agent and registrar for the Shares and registered by such transfer agent and registrar and will conform to the specimen certificate examined by us evidencing the Shares.

Based upon the foregoing, and subject to the qualifications, assumptions and limitations stated herein, we are of the opinion that the Shares are duly authorized, validly issued, fully paid and nonassessable.

We are members of the bar of the State of Texas, and we do not express any opinion herein concerning any law other than the Delaware General Corporation Law.

This opinion letter speaks only as of its date and is delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act. We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the use of our name under the caption “Legal Matters” in the Prospectus included in the Registration Statement. In giving such consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act, and the rules and regulations of the SEC promulgated thereunder.

Very truly yours,

/s/ Jackson Walker L.L.P.

JACKSON WALKER L.L.P.

SLC/srj/law