Exhibit 4.1

STOCKHOLDERS’ AGREEMENT

DATED AS OF

OCTOBER 9, 2014

AMONG

DAVE & BUSTER’S ENTERTAINMENT, INC.

AND

THE STOCKHOLDERS PARTY HERETO

Table of Contents

i

THIS STOCKHOLDERS’ AGREEMENT (this “Agreement”)

dated as of October 9, 2014 among:

(i) Dave & Buster’s Entertainment, Inc. (f/k/a Dave & Buster’s Parent, Inc.), a Delaware corporation (the “Company”); and

(ii) Oak Hill Capital Partners III, L.P. and Oak Hill Capital Management Partners III, L.P. (collectively, with their permitted assignees as contemplated by Section 4.01(b), “Oak Hill”).

W I T N E S S E T H :

WHEREAS, in connection with underwritten initial public offering of Common Stock of the Company (the “Initial Public Offering”), it is the intention of the parties hereto to enter into this Agreement to govern Oak Hill’s rights with respect to the Company.

NOW, THEREFORE, for good and valuable consideration the sufficiency and adequacy of which is hereby acknowledged, the parties hereto agree as follows:

ARTICLE 1

DEFINITIONS

Section 1.01. Definitions.

(a) The following terms, as used herein, have the following meanings:

“Affiliate” means, with respect to any Person, any other Person directly or indirectly controlling, controlled by or under common control with such Person; provided that no securityholder of the Company shall be deemed an Affiliate of any other securityholder solely by reason of an investment in the Company. For the purpose of this definition, the term “control” (including, with correlative meanings, the terms “controlling”, “controlled by” and “under common control with”), as used with respect to any Person, shall mean the possession, directly or indirectly, of the power to direct or cause the direction of the management and policies of such Person, whether through the ownership of voting securities, by contract or otherwise.

“Board” means the board of directors of the Company.

“Business Day” means any day except a Saturday, Sunday or other day on which commercial banks in New York City are authorized by law to close.

“Charter” means the Second Amended and Restated Certificate of Incorporation of the Company, as the same may be amended from time to time.

“Common Shares” means shares of Common Stock.

“Common Stock” means the Company’s common stock, par value $0.01 per share, and any stock into which such Common Stock may thereafter be converted, changed, reclassified or exchanged.

“Company Securities” means (i) the Common Stock, (ii) any preferred stock, (iii) any other common stock issued by the Company and (iv) any securities convertible into or exchangeable for, or options, warrants or other rights to acquire, Common Stock or any other common stock issued by the Company.

“Designation Number” means (i) the product of (x) Oak Hill’s aggregate ownership interest in the Company multiplied by (y) the then current number of directors on the Board and (ii) then rounded to the next highest number of directors if the product of clause (x) and (y) does not equal a whole number. For illustrative purposes only, if Oak Hill’s aggregate ownership percentage is 60% and there are 9 directors, the product of (x) and (y) would equal 5.4 and the Designation Number would be 6 directors.

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

“Oak Hill Nominees” means the members of the Board designated by Oak Hill.

“Person” means an individual, corporation, limited liability company, partnership, association, trust or other entity or organization, including a government or political subdivision or an agency or instrumentality thereof.

“Relevant Stock Exchange” means the primary U.S. stock exchange on which the Company’s Common Stock is listed.

“Securities Act” means the Securities Act of 1933, as amended.

“Stockholder” means each Person (other than the Company) who, at any relevant determination date, shall be a party to or bound by this Agreement (as may be amended from time to time) so long as such Person shall “beneficially own” (as such term is defined in Rule 13d-3 of the Exchange Act) any Company Securities.

“Subsidiary” means, with respect to any Person, any entity of which securities or other ownership interests having ordinary voting power to elect a majority of the board of directors or other persons performing similar functions are at the time directly or indirectly owned by such Person.

“Transfer” means, with respect to any Company Securities, (i) when used as a verb, to sell, assign, dispose of, exchange, pledge, encumber, hypothecate or otherwise transfer such Company Securities or any participation or interest therein, whether directly or indirectly, or agree or commit to do any of the foregoing and (ii) when used as a noun, a direct or indirect sale, assignment, disposition, exchange, pledge, encumbrance, hypothecation, or other transfer of such Company Securities or any participation or interest therein or any agreement or commitment to do any of the foregoing.

2

(b) Each of the following terms is defined in the Section set forth opposite such term:

(c) Other Definitional and Interpretive Matters. Unless otherwise expressly provided, for purposes of this Agreement, the following rules of interpretation shall apply:

Calculation of Time Period. When calculating the period of time before which, within which or following which any act is to be done or step taken pursuant to this Agreement, the date that is the reference date in calculating such period shall be excluded. If the last day of such period is a non-Business Day, the period in question shall end on the next succeeding Business Day.

Dollars. Any reference in this Agreement to $ shall mean U.S. dollars.

Exhibits/Schedules. The Exhibits and Schedules to this Agreement are hereby incorporated and made a part hereof and are an integral part of this Agreement. All Exhibits, Annexes and Schedules annexed hereto or referred to herein are hereby incorporated in and made a part of this Agreement as if set forth in full herein. Any capitalized terms used in any Schedule, Annex or Exhibit but not otherwise defined therein shall be defined as set forth in this Agreement.

Gender and Number. Any reference in this Agreement to gender shall include all genders, and words imparting the singular number only shall include the plural and vice versa.

Headings. The provision of a Table of Contents, the division of this Agreement into Articles, Sections and other subdivisions and the insertion of headings are for convenience of reference only and shall not affect or be utilized in construing or interpreting this Agreement. All references in this Agreement to any “Section” are to the corresponding Section of this Agreement unless otherwise specified.

Herein. The words such as “herein,” “hereinafter,” “hereof,” and “hereunder” refer to this Agreement as a whole and not merely to a subdivision in which such words appear unless the context otherwise requires.

Including. Wherever the word “include,” “includes,” or “including” is used in this Agreement, it shall be deemed to be followed by the words “without limitation”.

3

ARTICLE 2

CORPORATE GOVERNANCE

Section 2.01. Board of Directors; Board Nominees; Committees.

(a) Concurrently with the Initial Public Offering, (i) the Board of the Company shall consist of the following nine (9) directors: Tyler J. Wolfram, Kevin M. Mailender, Alan J. Lacy, David A. Jones, Kevin M. Sheehan, Jonathan S. Halkyard, Michael J. Griffith, J. Taylor Crandall, and Stephen M. King, (ii) the Chairman of the Board shall be Alan J. Lacy and (iii) the lead independent director shall be Alan J. Lacy.

(b) Subject to applicable law and the Relevant Stock Exchange rules, Oak Hill shall be entitled to designate directors to serve on the Board proportionate to Oak Hill’s aggregate ownership interest in the Company, which such number of director designees shall be equal to the Designation Number; provided that as long as Oak Hill owns 5% or more of the issued and outstanding Common Stock of the Company, Oak Hill shall be entitled to designate to the Board at least one (1) director. As of the date hereof, Tyler J. Wolfram, Kevin M. Mailender and J. Taylor Crandall are the Oak Hill Nominees.

(c) Subject to applicable law and the Relevant Stock Exchange rules, (1) the Board shall have at least the following committees and (2) subject to Section 2.01(c)(i) and Section (c)(ii), each committee of the Board shall have at least one (1) member designated by Oak Hill.

(i) For so long as Oak Hill owns 20% or more of the issued and outstanding Common Stock of the Company, the Nominating and Corporate Governance Committee shall consist of no more than three (3) members. Oak Hill shall have the right to designate the members of the Nominating and Corporate Governance Committee up to the number of Oak Hill Nominees and the remaining members shall be appointed by the Board. The members of the Nominating and Corporate Governance Committee shall initially be Tyler J. Wolfram, Alan J. Lacy and Kevin M. Mailender.

(ii) Audit Committee which shall consist of members appointed by the Board. The members of the Audit Committee shall initially be Kevin M. Sheehan, Jonathan S. Halkyard and Michael J. Griffith. The Chairman of the Audit Committee shall initially be Kevin M. Sheehan.

(iii) Compensation Committee which shall consist of members appointed by the Board. The members of the Compensation Committee shall initially be Tyler J. Wolfram, David A. Jones, Alan J. Lacy, Michael J. Griffith and Jonathan S. Halkyard. The Chairman of the Compensation Committee shall initially be David A. Jones.

(iv) Plan Subcommittee of the Compensation Committee which shall consist of members appointed by the Board. The members of the Plan Committee shall initially be Michael J. Griffith and Jonathan S. Halkyard.

(d) The Company agrees to cause each individual designated pursuant to this Section 2.01 or Section 2.02 to be nominated to serve as a director on the Board, or as Chairman of the Board, and to take all other necessary actions (including calling a special meeting of the Board and/or stockholders or expanding the size of the Board) to ensure that the composition of the Board and any committee of the Board, as applicable, is as set forth in this Section 2.01 and to

4

otherwise implement the provisions of this Section 2.01 and Section 2.02. For the avoidance of doubt, the Company agrees to expand the size of the Board to ensure that that the composition of the Board is as set forth in Section 2.01(b).

Section 2.02. Vacancies. If, as a result of death, disability, retirement, resignation, removal or otherwise, there shall exist or occur any vacancy of an Oak Hill Nominee on the Board, Oak Hill may designate another individual (the “Replacement Nominee”) to fill such vacancy and serve as a director on the Board.

Section 2.03. Reimbursement of Director Expenses. The Company will pay all reasonable out-of-pocket expenses incurred by the Oak Hill Nominees in connection with traveling to and from and attending meetings of the Board (and any committee thereof) and while conducting business at the request of the Company.

Section 2.04. Reimbursement of Certain Oak Hill Expenses. The Company shall reimburse Oak Hill and its Affiliates for the costs of any third party advisors retained by Oak Hill and its Affiliates, and for any out of pocket expenses incurred in connection with (i) counsel retained by Oak Hill to advise the Oak Hill Nominees and/or the Company in connection with any matter related to or arising out of meetings of the Board (or committees thereof) or otherwise raised by management, (ii) any review, amendment and or enforcement of this Agreement, (iii) the agreements entered into in connection with the Initial Public Offering and the transactions contemplated hereby and thereby (including, the enforcement or amendment thereof) and (iv) any regulatory filings of the Company involving Oak Hill and/or its Affiliates (including any liquor license filings or securities filings (13D, Form 4 etc.)) and similar matters.

Section 2.05. Corporate Opportunities. In furtherance of, and without limiting what is set forth in the Charter, each of the parties hereto acknowledges that Oak Hill, its Affiliates and any related investment funds and portfolio companies may review the business plans and related proprietary information of any enterprise, including any enterprise which may have products or services which compete directly or indirectly with those of the Company or any of its Affiliates or Subsidiaries and may trade in the securities of such enterprise. Nothing in this Agreement shall preclude or in any way restrict Oak Hill, its Affiliates or any related investment funds or portfolio companies from investing or participating in any particular enterprise, or trading in the securities thereof whether or not such enterprise has products or services that compete with those of the Company or any of its Affiliates or Subsidiaries. Notwithstanding anything to the contrary herein, the Company expressly acknowledges and agrees that: (a) Oak Hill, members of the Board designated by Oak Hill and Affiliates or portfolio companies of Oak Hill, have the right to, and shall have no duty (contractual or otherwise) not to, directly or indirectly, engage in the same or similar business activities or lines of business as the Company or any of its Affiliates or Subsidiaries; and (b) in the event that Oak Hill, members of the Board designated by Oak Hill or any Affiliate or portfolio company of Oak Hill acquires knowledge of a potential transaction or matter that may be a corporate opportunity for any of the Company or any of its Affiliates or Subsidiaries, Oak Hill, members of the Board designated by Oak Hill or Affiliates or portfolio companies of Oak Hill shall have no duty (contractual or otherwise) to communicate or present such corporate opportunity to the Company or any of its Affiliates or Subsidiaries, as the case may be (provided, however, that the foregoing shall not apply to any person who is a director or officer of the Company if such business opportunity is expressly offered to such director or

5

officer solely in his or her capacity as a director or officer of the Company), and, notwithstanding any provision of this Agreement to the contrary, shall not be liable to the Company or any of its Affiliates or Subsidiaries or any stockholders for breach of any duty (contractual or otherwise) by reason of the fact that Oak Hill, any Affiliate thereof or related investment fund or portfolio company thereof, directly or indirectly, pursues or acquires such opportunity for itself, directs such opportunity to another Person, or does not present such opportunity to the Company or any of its Affiliates or Subsidiaries.

Section 2.06. Approvals. For so long as Oak Hill owns 25% or more of the issued and outstanding Common Stock of the Company, the Company and its Subsidiaries shall not take any of the following actions without the prior written consent of Oak Hill:

(a) declare or pay any non-pro rata dividends or other non-pro rata distributions or purchases in respect of the Company Securities; or

(b) amend the Charter or bylaws of the Company in a manner adverse to Oak Hill.

ARTICLE 3

CONFIDENTIAL INFORMATION

Section 3.01. Confidentiality.

(a) The Company acknowledges and agrees that (i) Oak Hill may disclose Confidential Information to its Affiliates, representatives and advisors, (ii) any Oak Hill Nominee may disclose Confidential Information to Oak Hill and its Affiliates, representatives and advisors, (iii) Oak Hill and its Affiliates may disclose Confidential Information if requested or required by law, judicial or governmental order, deposition, interrogatory, subpoena, civil investigation, demand, discovery request or similar process and (iv) Oak Hill and its Affiliates may disclose Confidential Information to any potential purchaser of the Company and/or Oak Hill’s Company Securities, that executes a customary confidentiality agreement. Oak Hill shall have no obligation to the Company to disclose discussions with any potential purchaser of its Company Securities. For so long as Oak Hill owns 10% or more of the issued and outstanding Common Stock of the Company, Oak Hill will be granted access to customary non-public information of the Company and its Subsidiaries and members of the Company’s and its Subsidiaries’ management team as reasonably requested by Oak Hill.

(b) “Confidential Information” shall mean any confidential or proprietary information relating to the business or affairs of the Company or any of its Affiliates, including, but not limited to, information relating to financial statements, customer identities, potential customers, employees, sales representatives, suppliers, servicing methods, equipment programs, strategies and information, analyses, profit margins or other proprietary information used by the

6

Company or any of its Affiliates; provided, however, that Confidential Information does not include any information which is in the public domain or becomes known in the industry through no wrongful act on the part of Oak Hill; provided that Confidential Information shall not include information that (i) is or becomes generally known to the public other than as a result of a disclosure by Oak Hill in violation of this Agreement, (ii) is or was available to Oak Hill on a non-confidential basis prior to its disclosure to Oak Hill, or (iii) was or becomes available to Oak Hill on a non-confidential basis from a source other than the Company, which source is or was (at the time of receipt of the relevant information) not bound by a confidentiality agreement with the Company or another person.

ARTICLE 4

MISCELLANEOUS

Section 4.01. Binding Effect; Assignability; Benefit.

(a) This Agreement shall inure to the benefit of and be binding upon the parties hereto and their respective heirs, successors, legal representatives and permitted assigns.

(b) Neither this Agreement nor any right, remedy, obligation or liability arising hereunder or by reason hereof shall be assignable by any party hereto pursuant to any Transfer of Company Securities or otherwise; provided, however, that in connection with any Transfer of Company Securities by Oak Hill (i) to any of its Affiliates or (ii) in a privately negotiated transaction, in each case Oak Hill may assign all or any portion of its rights as set forth in Article 2 and Article 3 to any transferee who agrees to be bound by this Agreement.

(c) Nothing in this Agreement, expressed or implied, is intended to confer on any Person other than the parties hereto, and their respective heirs, successors, legal representatives and permitted assigns, any rights, remedies, obligations or liabilities under or by reason of this Agreement.

Section 4.02. Notices. All notices, requests and other communications to any party shall be in writing and shall be delivered in person, mailed by certified or registered mail, return receipt requested, or sent by facsimile transmission,

If to the Company, to:

Dave & Buster’s Entertainment, Inc.

2481 Manana Drive

Dallas, Texas 75220

Attention: Jay L. Tobin, Esq.

Fax: (214) 357-1536

With a copy to:

Oak Hill Capital Management, LLC

65 East 55th Street, 32nd Floor

New York, NY 10022

Attention: John R. Monsky, Esq.

Fax: (212) 527-8450

7

and

Weil, Gotshal & Manges LLP

767 Fifth Avenue

New York, New York 10153

Attention: Douglas P. Warner, Esq.

Fax: (212) 310-8007

If to Oak Hill, to:

Oak Hill Capital Management, LLC

65 East 55th Street, 32nd Floor

New York, NY 10022

Attention: John R. Monsky, Esq.

Fax: (212) 527-8450

With a copy to:

Weil, Gotshal & Manges LLP

767 Fifth Avenue

New York, New York 10153

Attention: Douglas P. Warner, Esq.

Fax: (212) 310-8007

or, in each case, at such other address or fax number as such party may hereafter specify for the purpose of notices hereunder by written notice to the other parties hereto. All notices, requests and other communications shall be deemed received on the date of receipt by the recipient thereof if received prior to 5:00 p.m. in the place of receipt and such day is a Business Day in the place of receipt. Otherwise, any such notice, request or communication shall be deemed not to have been received until the next succeeding Business Day in the place of receipt. Any notice, request or other written communication sent by facsimile transmission shall be confirmed by certified or registered mail, return receipt requested, posted within one (1) Business Day, or by personal delivery, whether courier or otherwise, made within two (2) Business Days after the date of such facsimile transmissions.

Any Person that hereafter becomes a Stockholder shall provide its address and fax number to the Company, which shall promptly provide such information to each other Stockholder.

Section 4.03. Waiver; Amendment; Termination.

(a) No provision of this Agreement may be waived except by an instrument in writing executed by the party against whom the waiver is to be effective. No provision of this Agreement may be amended or otherwise modified except by an instrument in writing executed by the Company and Oak Hill.

8

(b) This Agreement shall terminate upon, (i) the written request of Oak Hill or (ii) such time as Oak Hill or any transferee of Oak Hill who agrees to be bound by this Agreement owns less than 5% in the aggregate of the issued and outstanding Common Stock of the Company.

Section 4.04. Fees and Expenses. Except as set forth in Section 2.04, each party shall pay its own costs and expenses incurred in connection with the preparation and execution of this Agreement.

Section 4.05. Governing Law. This Agreement, and all claims or causes of action (whether at law, in equity, in contract, in tort or otherwise) based upon, arising out of, related to or otherwise in connection with this Agreement or the transactions contemplated hereby, shall be exclusively governed by, and construed in accordance with, the internal laws of the State of Delaware, without giving effect to principles or rules of conflict of laws to the extent such principles or rules would require or permit the application of laws of another jurisdiction (including any claim or cause of action based upon, arising out of or related to any representation or warranty made in or in connection with this Agreement or as an inducement to enter into this Agreement).

Section 4.06. Jurisdiction. The parties hereby agree that any suit, action or proceeding (whether at law, in equity, in contract, in tort or otherwise) seeking to enforce any provision of, or based on any matter arising out of or in connection with, this Agreement or the transactions contemplated hereby (including any claim or cause of action based upon, arising out of or related to any representation or warranty made in or in connection with this Agreement or as an inducement to enter into this Agreement) shall be exclusively brought in the United States District Court for the Southern District of New York or any New York State court sitting in New York City, so long as one of such courts shall have subject matter jurisdiction over such suit, action or proceeding, and that any case of action arising out of this Agreement shall be deemed to have arisen from a transaction of business in the State of New York, and each of the parties hereby irrevocably consents to the exclusive jurisdiction of such courts (and of the appropriate appellate courts therefrom) in any such suit, action or proceeding and irrevocably waives, to the fullest extent permitted by law, any objection that it may now or hereafter have to the laying of the venue of any such suit, action or proceeding in any such court or that any such suit, action or proceeding which is brought in any such court has been brought in an inconvenient form. Process in any such suit, action or proceeding may be served on any party anywhere in the world, whether within or without the jurisdiction of any such court. Without limiting the foregoing, each party agrees that service of process on such party as provided in Section 4.03 shall be deemed effective service of process on such party.

Section 4.07. Waiver of Jury Trial. EACH OF THE PARTIES HERETO HEREBY IRREVOCABLY WAIVES ANY AND ALL RIGHT TO TRIAL BY JURY IN ANY LEGAL PROCEEDING (WHETHER AT LAW, IN EQUITY, IN CONTRACT, IN TORT OR OTHERWISE) ARISING OUT OF OR RELATED TO THIS AGREEMENT OR THE TRANSACTIONS CONTEMPLATED HEREBY.

Section 4.08. Specific Enforcement; Cumulative Remedies. The parties hereto acknowledge that money damages may not be an adequate remedy for violations of this

9

Agreement and that any party, in addition to any other rights and remedies which the parties may have hereunder or at law or in equity, may, in his or its sole discretion, apply to a court of competent jurisdiction for specific performance or injunction or such other relief as such court may deem just and proper in order to enforce this Agreement or prevent any violation hereof and, to the extent permitted by applicable law, each party waives any objection to the imposition of such relief. All rights, powers and remedies provided under this Agreement or otherwise available in respect hereof at law or in equity shall be cumulative and not alternative, and the exercise or beginning of the exercise of any thereof by any party shall not preclude the simultaneous or later exercise of any other such rights, powers or remedies by such party.

Section 4.09. Entire Agreement. This Agreement and any exhibits and other documents referred to herein constitute the entire agreement and understanding among the parties hereto in respect of the subject matter hereof and thereof and supersede all prior and contemporaneous agreements and understandings, both oral and written, among the parties hereto, or between any of them, with respect to the subject matter hereof and thereof.

Section 4.10. Severability. If any term, provision, covenant or restriction of this Agreement is held by a court of competent jurisdiction or other authority to be invalid, void or unenforceable, the remainder of the terms, provisions, covenants and restrictions of this Agreement shall remain in full force and effect and shall in no way be affected, impaired or invalidated. Upon such a determination, the parties shall negotiate in good faith to modify this Agreement so as to effect the original intent of the parties as closely as possible in an acceptable manner so that the transactions contemplated hereby be consummated as originally contemplated to the fullest extent possible.

Section 4.11. Counterparts; Effectiveness. This Agreement may be executed in any number of counterparts, each of which shall be deemed to be an original, with the same effect as if the signatures thereto and hereto were upon the same instrument.

Section 4.12. No Recourse. Notwithstanding anything that may be expressed or implied in this Agreement, and notwithstanding the fact that the entities comprising Oak Hill are two limited partnerships, each party to this Agreement covenants, agrees and acknowledges that no recourse under this Agreement or any documents or instruments delivered in connection with this Agreement shall be had against any of Oak Hill’s current or future directors, officers, employees, general or limited partners, members, managers or trustees, or any partner, member, manager or trustee, as such, whether by the enforcement of any assessment or by any legal or equitable proceeding, or by virtue of any statute, regulation or other applicable law, it being expressly agreed and acknowledged that no personal liability whatsoever shall attach to, be imposed on or otherwise be incurred by any of Oak Hill’s current or future officers, agents, employees, directors, managers, members, or any Affiliates or assignees thereof, as such, for any obligation of Oak Hill under this Agreement or any documents or instruments delivered in connection with this Agreement for any claim based on, in respect of or by reason of such obligations or their creation.

[The remainder of this page is intentionally left blank.]

10

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be duly executed by their respective authorized officers as of the day and year first above written.

[SIGNATURE PAGE TO STOCKHOLDERS AGREEMENT]