Exhibit 10.4

VOTING AGREEMENT

This VOTING AGREEMENT (this “Agreement”), dated as of October 1, 2014, is entered into by and among CST Brands, Inc., a Delaware corporation (“CST”), and each of the persons listed on the signature page hereto (each, an “Equityholder”). Each Equityholder and CST are referred to collectively in this Agreement as the “Parties” and each individually as a “Party.”

RECITALS

WHEREAS, as of the date of this Agreement, each Equityholder is, except as set forth on Annex I, the beneficial owner (as defined in Rule 13d-3 under the Securities Exchange Act of 1934, as amended (the “Exchange Act”), it being understood that “beneficially owned” and “beneficial ownership” shall have correlative meanings) of the number of shares of CST common stock, par value $0.01 per share (“CST Common Stock”), and/or common units or subordinated units (“Partnership Units”) of Lehigh Gas Partners LP, a publicly traded Delaware limited partnership (the “Partnership”), set forth opposite such Equityholder’s name under the headings “Shares of CST Common Stock Beneficially Owned” and “Partnership Common Units and Subordinated Units Beneficially Owned” on Annex I (all such beneficially owned shares of CST Common Stock or Partnership Units that are outstanding as of the date of this Agreement and any outstanding shares of CST Common Stock or Partnership Units that may hereafter be acquired by such Equityholder pursuant to acquisition by purchase, dividend, distribution, split, split-up, combination, merger, consolidation, reorganization, recapitalization or similar transaction, being referred to herein as the “Subject Shares”; provided, however, that “Subject Shares” shall not include shares of CST Common Stock or Partnership Units beneficially owned in the form of CST or Partnership equity awards (other than CST restricted stock), including equity awards in any affiliate of the Partnership that are substantially related to the performance by or on behalf of the Partnership, pursuant to any equity incentive plan of CST or the Partnership or any such affiliate, so long as such CST or Partnership equity awards remain unexercised);

WHEREAS, entry into this Agreement is a condition to the closing of the transactions contemplated by that certain IDR Purchase Agreement, dated as of August 6, 2014 (the “IDR Purchase Agreement”), by and among one of the Equityholders, the Reilly Trust (as defined in the IDR Purchase Agreement), CST and CST Holdings, LLC, a Delaware limited liability company and wholly owned subsidiary of CST (“IDR Buyer”), and that certain GP Purchase Agreement, dated as of August 6, 2014 (the “GP Purchase Agreement” and together with the IDR Purchase Agreement, the “Purchase Agreements”), by and among one of the Equityholders, CST and CST GP, LLC, a Delaware limited liability company and wholly owned subsidiary of CST (“GP Buyer”);

WHEREAS, in connection with the closing of the transactions contemplated by the Purchase Agreements, Joseph V. Topper, Jr. has been elected to the Board of Directors of CST;

WHEREAS, the Equityholders who hold CST Common Stock are subject to certain restrictions on transfer pursuant to the IDR Purchase Agreement; and

WHEREAS, the Equityholders who hold Partnership Units are subject to and bound by the terms and conditions of the Partnership Agreement (as defined in the GP Purchase Agreement).

NOW, THEREFORE, in consideration of the premises and of the mutual promises, representations, warranties, covenants, conditions and agreements contained herein, and for other valuable consideration, the receipt and sufficiency of which are hereby acknowledged, CST and the Equityholders, intending to be legally bound by the terms of this Agreement, hereby agree as follows:

ARTICLE I

AGREEMENTS OF CST AND EACH EQUITYHOLDER

Section 1.1 Voting of Subject Shares. Each Equityholder irrevocably and unconditionally agrees that during the term of this Agreement such Equityholder shall, at any meeting (whether annual or special and whether or not an adjourned or postponed meeting) of the holders of shares of CST Common Stock or Partnership Units, however called (each, a “Meeting”) (or in connection with any written consent of equityholders in lieu of a Meeting), vote (or cause to be voted) such Equityholder’s Subject Shares in accordance with the recommendations of:

(a) with respect to the shares of CST Common Stock held by such Equityholder, the Board of Directors of CST; and

(b) with respect to the Partnership Units held by such Equityholder, the Board of Directors of the general partner of the Partnership.

Section 1.2 No Proxies for Subject Shares. Except as provided in this Agreement, during the term of this Agreement, each Equityholder shall not (nor permit any person under such Equityholder’s control to), directly or indirectly, grant any proxies or powers of attorney with respect to the right to vote, rights of first offer or refusal, or enter into any voting trust or voting agreement or arrangement, with respect to any of such Equityholder’s Subject Shares. Without limiting the foregoing, each Equityholder shall not take any other action that would in any way restrict, limit or interfere in any material respect with the performance of such Equityholder’s obligations under this Agreement.

Section 1.3 Documentation and Information. During the term of this Agreement, each Equityholder (a) consents to and authorizes the publication and disclosure by CST of such Equityholder’s identity and holdings of Subject Shares, the nature of such Equityholder’s commitments, arrangements and understandings under this Agreement and any other information, in each case, that CST reasonably determines is required to be disclosed by applicable legal requirements in any press release or any other disclosure document and (b) agrees to promptly give to CST any information CST may reasonably require for the preparation of any such disclosure documents. CST (i) consents to and authorizes the publication and disclosure by any Equityholder of CST’s identity, the nature of CST’s and such Equityholder’s commitments, arrangements and understandings under this Agreement and any other information, in each case, that such Equityholder reasonably determines is required to be disclosed by such Equityholder under applicable legal requirements in any Schedules 13D or 13G or amendments to Schedules 13D or 13G and filings under Section 16 of the Exchange Act and any other filings with or notices to governmental entities and (ii) agrees to promptly give to such Equityholder any information such Equityholder may reasonably request for the preparation of any such documents. Each Party to this Agreement agrees to promptly notify the other Parties of any required corrections with respect to any information supplied by such Party specifically for use in any such document, if and to the extent that any such information shall have become false or misleading in any material respect.

Section 1.4 Irrevocable Proxy. Each Equityholder hereby revokes (or agrees to cause to be revoked) any voting proxies that such Equityholder has heretofore granted with respect to such

2

Equityholder’s Subject Shares. Each Equityholder hereby irrevocably appoints CST as attorney-in-fact and proxy for and on behalf of such Equityholder, for and in the name, place and stead of such Equityholder, to: (a) vote or issue instructions to the record holder to vote, such Equityholder’s Subject Shares in accordance with the provisions of Section 1.1 at any and all Meetings and (b) grant or withhold, or issue instructions to the record holder to grant or withhold, in accordance with the provisions of Section 1.1, all written consents with respect to the Subject Shares in connection with any action sought to be taken by written consent without a meeting. CST agrees not to exercise the proxy granted herein for any purpose other than the purposes described in this Agreement. The foregoing proxy shall be deemed to be a proxy coupled with an interest, is irrevocable (and as such shall survive and not be affected by the death, incapacity, mental illness or insanity of such Equityholder, as applicable) until the termination of this Agreement and shall not be terminated by operation of legal requirements or upon the occurrence of any other event other than the termination of this Agreement with respect to such Equityholder pursuant to Section 4.2 (and shall be terminated and revoked upon such termination). Each Equityholder authorizes such attorney and proxy to substitute any other Person to act hereunder, to revoke any substitution and to file this proxy and any substitution or revocation with the secretary of CST. Each Equityholder hereby affirms that the proxy set forth in this Section 1.4 is given in connection with and granted in consideration of and as an inducement to CST to close the transactions contemplated by the Purchase Agreements and that such proxy is given to secure the obligations of the Equityholder under Section 1.1.

Section 1.5 CST Board Membership. The Board of Directors of CST (the “CST Board”) has undertaken all actions necessary, effective upon the closing of the transactions contemplated by the Purchase Agreements, to appoint Joseph V. Topper, Jr. as a Class I director on the CST Board.

Section 1.6 Further Assurances. Subject to the terms and conditions of this Agreement, CST and each Equityholder agrees to execute and deliver, or cause to be executed and delivered, all further documents and instruments, and use their respective commercially reasonable efforts to take, or cause to be taken, all actions and to do, or cause to be done, all things, in each case that are necessary, proper or advisable under applicable legal requirements and regulations to perform his, her or its obligations under this Agreement.

ARTICLE II

REPRESENTATIONS AND WARRANTIES OF EACH EQUITYHOLDER

Each Equityholder hereby, severally (but only in proportion to the percentage of shares of CST Common Stock or Partnership Units, as applicable, beneficially owned by such Equityholder as set forth on Annex I) and not jointly, represents and warrants to CST only as to himself, herself or itself (as the case may be) as follows:

Section 2.1 Organization. Such Equityholder, if not an individual, is duly organized and validly existing and in good standing under the laws of the jurisdiction of its organization. Such Equityholder, if an individual, is a resident of the state set forth below such Equityholder’s signature on the signature page hereto.

Section 2.2 Authorization. If such Equityholder is not an individual, it has full organizational power and authority to execute and deliver this Agreement and to perform its obligations hereunder. If such Equityholder is an individual, he or she has full legal capacity, right and authority to

3

execute and deliver this Agreement and to perform his or her obligations hereunder. If such Equityholder is not an individual, the execution, delivery and performance by such Equityholder of this Agreement and the consummation by such Equityholder of the transactions contemplated hereby have been duly authorized by all necessary action on the part of such Equityholder.

Section 2.3 Due Execution and Delivery; Binding Agreement. This Agreement has been duly executed and delivered by such Equityholder and constitutes a valid and legally binding obligation of such Equityholder, enforceable against such Equityholder in accordance with its terms, subject to the effects of bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar legal requirements relating to or affecting creditors’ rights generally and general equitable principles (whether considered in a proceeding in equity or at law).

Section 2.4 No Violation

(a) The execution and delivery of this Agreement by such Equityholder does not, and the performance by such Equityholder of such Equityholder’s obligations hereunder will not, (i) if such Equityholder is not an individual, contravene, conflict with, or result in any violation or breach of any provision of its organizational documents, (ii) assuming compliance with Section 2.4(b), contravene, conflict with or result in a violation or breach of any provision of applicable legal requirements or order of any governmental entity with competent jurisdiction or (iii) constitute a default, or an event that, with or without notice or lapse of time or both, will become a default, under, or cause or permit the termination, cancellation or acceleration of any right or obligation under any provision of any agreement binding upon such Equityholder, except, in the case of clauses (ii) and (iii), as would not reasonably be expected to impair in any material respect the ability of such Equityholder to perform his, her or its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

(b) No consent, approval, order, authorization or permit of, or registration, declaration or filing with or notification to, any governmental entity or any other Person is required by or with respect to such Equityholder in connection with the execution and delivery of this Agreement by such Equityholder or the performance by such Equityholder of his, her or its obligations hereunder, except for the filing with the SEC of any Schedules 13D or 13G or amendments to Schedules 13D or 13G and filings under Section 16 of the Exchange Act as may be required in connection with this Agreement and the transactions contemplated hereby and except as would not reasonably be expected to impair in any material respect the ability of such Equityholder to perform his, her or its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

Section 2.5 Ownership of Subject Shares. As of the date of this Agreement, such Equityholder is a beneficial owner of, and such Equityholder or another Equityholder has good and valid title to, such Equityholder’s Subject Shares with no restrictions on such Equityholder’s rights of disposition pertaining thereto other than any restrictions under applicable securities laws or in connection with the arrangements described on Annex I. Other than as provided in this Agreement, such Equityholder has, with respect to such Equityholder’s Subject Shares, either (i) the sole power, directly or indirectly, to vote and dispose of such Subject Shares or (ii) the shared power together with one or more other Equityholder, directly or indirectly, to vote and dispose of such Subject Shares, and to issue instructions pertaining to such Subject Shares with respect to the matters set forth in this Agreement, in each case with no limitations, qualifications or restrictions on such rights other than any limitations, qualifications restrictions in connection with the arrangements described on Annex I, and, as such, has

4

the complete and exclusive power, individually or together with one or more other Equityholder, to, directly or indirectly (a) issue (or cause the issuance of) instructions with respect to the matters set forth in Section 1.4 of this Agreement and (b) agree to all matters set forth in this Agreement. None of such Equityholder’s Subject Shares are held in an account that would allow a third party to lend out such Subject Shares on any securities lending market or otherwise. Other than any shares of CST Common Stock or Partnership Units underlying CST or Partnership equity awards (other than CST restricted stock), the number of shares of CST Common Stock or Partnership Units set forth on Annex I opposite the name of such Equityholder are the only shares of CST Common Stock or Partnership Units beneficially owned by such Equityholder as of the date of this Agreement. Other than the Subject Shares and any shares of CST Common Stock or Partnership Units underlying CST or Partnership equity awards (other than CST restricted stock) (the number of which is set forth opposite the name of such Equityholder on Annex I under the heading “Shares Subject to CST Equity Awards (other than CST Restricted Stock)” and “Units Subject to Partnership Equity Awards”) or as set forth on Annex I, as of the date of this Agreement such Equityholder does not own any shares of CST Common Stock or Partnership Units or any options to purchase or rights to subscribe for or otherwise acquire any securities of CST or the Partnership and has no interest in or voting rights with respect to any securities of CST or the Partnership.

Section 2.6 No Other Proxies. None of such Equityholder’s Subject Shares are subject to any voting trust or other agreement or arrangement with respect to the voting of such Subject Shares, except as provided hereunder and except for any agreement or arrangement in connection with the arrangements set forth on Annex I.

Section 2.7 Absence of Litigation. With respect to such Equityholder, as of the date of this Agreement, there is no action, suit, investigation or proceeding pending against, or, to the knowledge of such Equityholder, threatened against such Equityholder or any of his, her or its properties or assets (including such Equityholder’s Subject Shares) that would reasonably be expected to impair in any material respect the ability of such Equityholder to perform his, her or its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

Section 2.8 Reliance. Such Equityholder understands and acknowledges that CST has consummated the transactions contemplated by the Purchase Agreements in reliance upon such Equityholder’s execution, delivery and performance of this Agreement.

ARTICLE III

REPRESENTATIONS AND WARRANTIES OF CST

CST hereby represents and warrants to the Equityholders that:

Section 3.1 Organization. CST is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization.

Section 3.2 Authorization. CST has full corporate power and authority to execute and deliver this Agreement and to perform its obligations hereunder. The execution, delivery and performance by CST of this Agreement and the consummation by CST of the transactions contemplated hereby have been duly authorized by all necessary action on the part of CST.

5

Section 3.3 Due Execution and Delivery; Binding Agreement. This Agreement has been duly executed and delivered by CST and constitutes a valid and legally binding obligation of CST, enforceable against CST in accordance with its terms, subject to the effects of bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar legal requirements relating to or affecting creditors’ rights generally and general equitable principles (whether considered in a proceeding in equity or at law).

Section 3.4 No Violation

(a) The execution and delivery of this Agreement by CST does not, and the performance by CST of its obligations hereunder will not, (i) contravene, conflict with, or result in any violation or breach of any provision of its organizational documents, (ii) contravene, conflict with or result in a violation or breach of any provision of applicable legal requirements or order of any governmental entity with competent jurisdiction or (iii) constitute a default, or an event that, with or without notice or lapse of time or both, will become a default, under, or cause or permit the termination, cancellation or acceleration of any right or obligation under any provision of any agreement binding upon CST, except, in the case of clauses (ii) and (iii), as would not reasonably be expected to impair in any material respect the ability of CST to perform its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

(b) No consent, approval, order, authorization or permit of, or registration, declaration or filing with or notification to, any governmental entity or any other Person is required by or with respect to CST in connection with the execution and delivery of this Agreement by CST or the performance by CST of its obligations hereunder, except as would not reasonably be expected to impair in any material respect the ability of CST to perform its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

Section 3.5 Absence of Litigation. As of the date of this Agreement, there is no action, suit, investigation or proceeding pending against, or, to the knowledge of CST, threatened against CST or any of its properties or assets that would reasonably be expected to impair in any material respect the ability of CST to perform its obligations hereunder or to consummate the transactions contemplated hereby on a timely basis.

Section 3.6 Reliance. CST understands and acknowledges that the Equityholders have consummated the transactions contemplated by the Purchase Agreements in reliance upon CST’s execution, delivery and performance of this Agreement.

ARTICLE IV

MISCELLANEOUS

Section 4.1 Notices. All notices, requests and other communications to any Party shall be in writing (including facsimile transmission) and shall be given to CST or to such Equityholder at CST’s or such Equityholder’s address, facsimile number or electronic mail address set forth on a signature page hereto, or to such other address, facsimile number or electronic mail address as such Party may hereafter specify for the purpose by notice to each other Party hereto.

Section 4.2 Term. This Agreement shall remain in full force and effect with respect to any Equityholder for so long as such Equityholder is (a) a director or officer of CST or any affiliate of CST,

6

including the Partnership, (b) the beneficial owner of more than 3% of the outstanding CST Common Stock or (c) the beneficial owner of 10% or more of the outstanding Partnership Units. Upon termination of this Agreement with respect to any Equityholder, such Equityholder shall have no further obligations or liabilities under this Agreement; provided, however, that (x) nothing set forth in this Section 4.2 shall relieve any Equityholder for liability arising from fraud or a willful breach of this Agreement and (y) the provisions of this Article IV shall survive any such termination of this Agreement.

Section 4.3 Amendments and Waivers. No amendment, modification, replacement, rescission, termination or cancellation of any provision of this Agreement will be valid, unless the same is in writing and signed by the Parties hereto. No waiver by either Party of any default, misrepresentation or breach of warranty or covenant under this Agreement or course of dealing between the Parties, whether intentional or not, will extend to any prior or subsequent default, misrepresentation, or breach of warranty or covenant under this Agreement or affect in any way any rights arising because of any prior or subsequent such occurrence. No single or partial exercise of any right or remedy under this Agreement precludes the simultaneous or subsequent exercise of any other right or remedy.

Section 4.4 Expenses. All costs and expenses incurred in connection with this Agreement shall be paid by the Party incurring or required to incur such cost or expenses.

Section 4.5 Binding Effect; Assignment. The provisions of this Agreement shall be binding upon and shall inure to the benefit of the Parties and their respective successors and permitted assigns. No Party may assign, delegate or otherwise transfer any of its rights or obligations under this Agreement without the consent of each other Party.

Section 4.6 Governing Law; Jurisdiction; Jury Waiver. This Agreement shall be governed by and construed in accordance with the internal and substantive Laws of the State of Delaware and without regard to any conflicts of Laws concepts that would apply the substantive Law of some other jurisdiction. To the fullest extent permitted by applicable Law, the Parties hereby irrevocably submit to the jurisdiction of the courts of the State of Delaware and of the federal courts of the United States of America located in Delaware over any dispute arising out of or relating to this Agreement or any of the transactions contemplated by this Agreement, and each Party irrevocably agrees that all claims in respect of such dispute or proceeding shall be heard and determined in such courts. The Parties hereby irrevocably waive, to the fullest extent permitted by applicable Law, any objection that they may now or hereafter have to the venue of any dispute arising out of or relating to this Agreement or any of the transactions contemplated by this Agreement brought in such court or any defense of inconvenient forum for the maintenance of such dispute. Each Party agrees that a judgment in any dispute heard in the venue specified by this section may be enforced in other jurisdictions by suit on the judgment or in any other manner provided by applicable Law. EACH OF THE PARTIES HEREBY IRREVOCABLY WAIVES, TO THE FULLEST EXTENT PERMITTED BY LAW, ANY AND ALL RIGHT TO TRIAL BY JURY IN ANY LEGAL PROCEEDING ARISING OUT OF OR RELATING TO THIS AGREEMENT.

Section 4.7 Signatures and Counterparts. Facsimile or electronic transmission of any signed original document and/or retransmission of any signed facsimile or electronic transmission shall be the same as delivery of an original. This Agreement may be executed in two or more counterparts, each of which shall be deemed an original and all of which together shall be considered one and the same agreement.

7

Section 4.8 Entire Agreement; Third Party Beneficiaries. This Agreement constitutes the entire agreement, and supersedes all prior agreements and understandings, both written and oral, between the Parties with respect to the subject matter of this Agreement. Nothing in this Agreement, express or implied, is intended to or shall confer upon any person other than the Parties and their respective successors and permitted assigns any right, benefit or remedy hereunder.

Section 4.9 Severability. This Agreement shall be deemed severable, and the invalidity or unenforceability of any specific term or provision of this Agreement shall not affect the validity or enforceability of this Agreement or of any other term or provision of this Agreement. Furthermore, in lieu of any such invalid or unenforceable term or provision, the Parties shall negotiate in good faith to modify this Agreement to include a provision as similar in terms to such invalid or unenforceable provision as may be possible and be valid and enforceable.

Section 4.10 Specific Performance. The Parties hereto agree that CST and the Equityholders would be irreparably damaged in the event that any Equityholder or CST, as applicable, fails to perform any of his, her or its obligations under this Agreement. Accordingly, CST and the Equityholders shall be entitled to an injunction or injunctions to prevent breaches of this Agreement by any Equityholder or CST, as applicable, and to specific performance of the terms and provisions of this Agreement in any court of competent jurisdiction, this being in addition to any other remedy to which they are entitled at law or in equity.

Section 4.11 Capacity as Stockholder or Unitholder; No Agreement as a Director or Officer. Notwithstanding anything in this Agreement to the contrary (including Section 1.6), each Equityholder signs this Agreement and makes the representations, warranties, covenants and agreements and undertakes the obligations and agreements set forth herein solely in such Equityholder’s capacity as a stockholder of CST and/or unitholder of the Partnership and not in such Equityholder’s capacity (directly or through its officers, employees, agents or representatives) as a director, officer or employee of CST, the Partnership or any of its or their subsidiaries or in such Equitholder’s capacity as a trustee or fiduciary of any employee benefit plan or trust. Notwithstanding anything in this Agreement to the contrary, nothing herein shall in any way restrict a director or officer of CST, the Partnership or of any of their subsidiaries in the exercise of his or her fiduciary duties as a director or officer of CST, the Partnership or of any of their subsidiaries or in his or her capacity as a trustee or fiduciary of any employee benefit plan or trust or prevent any director or officer of CST, the Partnership or of any of their subsidiaries or any trustee or fiduciary of any employee benefit plan or trust from taking or omitting to take, or be construed to create any obligation on the part of such person to take or omit to take, any action in his or her capacity as such director, officer, trustee or fiduciary for an employee benefit plan or trust, and no such action or omission shall constitute a breach of this Agreement or otherwise result in any liability on the part of such Equityholder.

Section 4.12 No Ownership Interest. All rights, ownership and economic benefits of and relating to the Subject Shares shall remain vested in and belong to such Equityholder, and CST shall have no authority to exercise any power or authority to direct such Equityholder in the voting of any of the Subject Shares, except as otherwise specifically provided herein.

8

Section 4.13 Interpretation. Unless the context requires otherwise: (a) any pronoun used in this Agreement shall include the corresponding masculine, feminine or neuter forms, and the singular form of nouns, pronouns and verbs, including any defined terms in this Agreement, shall include the plural and vice versa; (b) references to Articles and Sections refer to Articles and Sections of this Agreement; (c) references to Schedules and Exhibits refer to the Schedules and Exhibits attached to this Agreement, each of which is made a part of this Agreement for all purposes; (d) the terms “include”, “includes”, “including” and words of like import shall be deemed to be followed by the words “without limitation”; (e) the terms “hereof,” “herein” and “hereunder” refer to this Agreement as a whole and not to any particular provision of this Agreement; and (f) references to money refer to legal currency of the United States of America. The Parties have participated jointly in negotiating and drafting this Agreement. In the event that an ambiguity or a question of intent or interpretation arises, this Agreement will be construed as if drafted jointly by the Parties, and no presumption or burden of proof will arise favoring or disfavoring any party by virtue of the authorship of any provision of this Agreement.

[Signature page follows.]

9

IN WITNESS WHEREOF, CST and the Equityholders have caused this Agreement to be duly executed and delivered as of the date first written above.

Signature Page to Voting Agreement

Annex I