Exhibit 4.1

STOCKHOLDERS’ AGREEMENT

by and between

TEAM HEALTH HOLDINGS, INC.

and

ENSEMBLE PARENT LLC

Dated as of December 15, 2009

Table of Contents

i

STOCKHOLDERS’ AGREEMENT

STOCKHOLDERS’ AGREEMENT, dated as of December 15, 2009, by and between Team Health Holdings, Inc., a Delaware corporation (the “Company”) and Ensemble Parent LLC, a Delaware limited liability company (“Ensemble Parent”).

BACKGROUND:

WHEREAS, the Company is currently contemplating an underwritten initial public offering (“IPO”) of shares of its Common Stock (as defined in Section 1.1);

WHEREAS, the Company will be converted from Team Health Holdings, LLC to a Delaware corporation in connection with the IPO of shares of its Common Stock; and

WHEREAS, in connection with, and effective upon, the date of completion of the IPO (the “Closing Date”) of the Company, the Company and Ensemble Parent wish to set forth certain understandings between such parties, including with respect to certain governance matters.

NOW, THEREFORE, the parties agree as follows:

ARTICLE I. INTRODUCTORY MATTERS

1.1 Defined Terms. In addition to the terms defined elsewhere herein, the following terms have the following meanings when used herein with initial capital letters:

“Affiliate” has the meaning ascribed thereto in Rule 12b-2 promulgated under the Exchange Act, as in effect on the date hereof.

“Agreement” means this Stockholders’ Agreement, as the same may be amended, supplemented, restated or otherwise modified from time to time in accordance with the terms hereof.

“Blackstone Designee” has the meaning set forth in Section 2.1(a).

“Blackstone Entities” means Ensemble Parent, its Affiliates and their respective successors and Permitted Assigns.

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

“Business Day” means a day other than a Saturday, Sunday, federal or New York State holiday or other day on which commercial banks in New York City are authorized or required by law to close.

“Closing Date” has the meaning set forth in the Background.

“Company” has the meaning set forth in the preamble.

“Common Stock” means the shares of common stock, par value $0.01 per share, of the Company, and any other capital stock of the Company into which such stock is reclassified or reconstituted and any other common stock of the Company.

“Control” (including its correlative meanings, “Controlled by” and “under common Control with”) means possession, directly or indirectly, of the power to direct or cause the direction of management or policies (whether through ownership of securities or partnership or other ownership interests, by contract or otherwise) of a Person.

“Director” means any member of the Board.

“Ensemble Parent” has the meaning set forth in the preamble.

“Exchange Act” means the Securities Exchange Act of 1934, as amended, and the rules and regulations promulgated thereunder, as the same may be amended from time to time.

“Governmental Authority” means any nation or government, any state or other political subdivision thereof, and any entity exercising executive, legislative, judicial, regulatory or administrative functions of or pertaining to government.

“IPO” has the meaning set forth in the Background.

“Law” means any statute, law, regulation, ordinance, rule, injunction, order, decree, governmental approval, directive, requirement, or other governmental restriction or any similar form of decision of, or determination by, or any interpretation or administration of any of the foregoing by, any Governmental Authority.

“Permitted Assigns” means with respect to Ensemble Parent, a Transferee of shares of Common Stock that agrees to become party to, and to be bound to the same extent as its transferor by the terms of, this Agreement.

“Person” means an individual, a partnership, a corporation, a limited liability company, an association, a joint stock company, a trust, a joint venture, an unincorporated organization and a governmental entity or any department, agency or political subdivision thereof.

“Subsidiary” means, with respect to any Person, any corporation, limited liability company, partnership, association or other business entity of which: (i) if a corporation, a majority of the total voting power of shares of stock entitled (without regard to the occurrence of any contingency) to vote in the election of directors, representatives or trustees thereof is at the time owned or Controlled, directly or indirectly, by that Person or one or more of the other Subsidiaries of that Person or a combination thereof; or (ii) if a limited liability company, partnership, association or other business entity, a majority of the total voting power of stock (or equivalent ownership interest) of the limited liability company, partnership, association or other business entity is at the time owned or Controlled, directly or indirectly, by any Person or one or more Subsidiaries of that Person or a combination thereof. For purposes hereof, a Person or Persons shall be deemed to have a majority ownership interest in a limited liability company, partnership, association or other business entity if such Person or Persons shall be allocated a majority of limited liability company, partnership, association or other business entity gains or losses or shall be or Control the managing director or general partner of such limited liability company, partnership, association or other business entity.

“Total Number of Directors” has the meaning set forth in Section 2.1(a).

“Transfer” (including its correlative meanings, “Transferor”, Transferee” and “Transferred”) shall mean, with respect to any security, directly or indirectly, to sell, contract to

2

sell, give, assign, hypothecate, pledge, encumber, grant a security interest in, offer, sell any option or contract to purchase, purchase any option or contract to sell, grant any option, right or warrant to purchase, lend or otherwise transfer or dispose of any economic, voting or other rights in or to such security. When used as a noun, “Transfer” shall have such correlative meaning as the context may require.

1.2 Construction. The language used in this Agreement will be deemed to be the language chosen by the parties to express their mutual intent, and no rule of strict construction will be applied against any party. Unless the context otherwise requires: (a) “or” is disjunctive but not exclusive, (b) words in the singular include the plural, and in the plural include the singular, and (c) the words “hereof”, “herein”, and “hereunder” and words of similar import when used in this Agreement refer to this Agreement as a whole and not to any particular provision of this Agreement, and Section references are to this Agreement unless otherwise specified.

ARTICLE II. CORPORATE GOVERNANCE MATTERS

2.1 Board of Directors. (a) Following the Closing Date, Ensemble Parent and/or its Permitted Assigns (as defined herein) shall have the right, but not the obligation, to nominate to the Board a number of designees equal to: (i) at least a majority of the total number of directors comprising the Board (the “Total Number of Directors”), so long as the Blackstone Entities collectively beneficially own 50% or more of the voting power of all shares of the Company’s capital stock entitled to vote generally in the election of Directors; (ii) 40% of the Total Number of Directors, in the event that the Blackstone Entities collectively beneficially own 40% or more, but less than 50%, of the voting power of all shares of the Company’s capital stock entitled to vote generally in the election of Directors; (iii) 30% of the Total Number of Directors, in the event that the Blackstone Entities collectively beneficially own 30% or more, but less than 40%, of the voting power of all shares of the Company’s capital stock entitled to vote generally in the election of Directors; (iv) 20% of the Total Number of Directors, in the event that the Blackstone Entities collectively beneficially own 20% or more, but less than 30%, of the voting power of all shares of the Company’s capital stock entitled to vote generally in the election of Directors; and (v) 10% of the Total Number of Directors, in the event that the Blackstone Entities collectively beneficially own 5% or more, but less than 20%, of the voting power of all shares of the Company’s capital stock entitled to vote generally in the election of Directors. For purposes of calculating the number of directors that Ensemble Parent (and/or its Permitted Assigns) is entitled to designate pursuant to the immediately preceding sentence, any fractional amounts shall automatically be rounded up to the nearest whole number (e.g., one and one quarter (1 ¹/4) Directors shall equate to two (2) Directors) and any such calculations shall be made on a pro forma basis, including, for the avoidance of doubt, taking into account any increase in the size of the Board. In the event that Ensemble Parent (and/or its Permitted Assigns) has nominated less than the total number of designees Ensemble Parent (and/or its Permitted Assigns) shall be entitled to nominate pursuant to this Section 2.1(a), Ensemble Parent (and/or its Permitted Assigns) shall have the right, at any time, to nominate such additional designees to which it is entitled, in which case, the Directors shall take all necessary corporation action to (x) enable Ensemble Parent (and/or its Permitted Assigns) to nominate such additional individuals, whether by increasing the size of the Board, subject to the maximum number of Directors set forth in Article VI, paragraph (A) of the Certificate of Incorporation of the Company, or otherwise and (y) to designate such additional individuals nominated by Ensemble Parent (and/or its Permitted Assigns) to fill such newly-created vacancies. Each such person whom Ensemble Parent (and/or its Permitted Assigns) shall actually nominate pursuant to this Section 2.1(a) and who is thereafter elected to the Board to serve as a Director shall be referred to herein as a “Blackstone Designee”).

(b) In the event, and each time, that the number of Directors whom Ensemble Parent (and/or its Permitted Assigns) has the right to nominate decreases by one pursuant to Section 2.1(a), one of the Blackstone Designees to the Board shall resign immediately or Ensemble Parent (and/or its Permitted Assigns) shall use its best efforts to cause such designee to resign.

3

(c) In the event that a vacancy is created at any time by the death, disability, retirement or resignation of any Director designated pursuant to this Section 2.1, the remaining Directors and the Company shall cause the vacancy created thereby to be filled by a new designee of Ensemble Parent (and/or its Permitted Assigns), if such Director was designated by Ensemble Parent (and/or its Permitted Assigns), as soon as possible, and the Company hereby agrees to take, at any time and from time to time, all actions necessary to accomplish the same.

(d) The Company agrees to include in the slate of nominees recommended by the Board the persons designated pursuant to this Section 2.1 and to use its best efforts to cause the election of each such designee to the Board, including nominating such individuals to be elected as Directors as provided herein.

ARTICLE III. COVENANTS

3.1 Books and Records; Access. The Company shall, and shall cause its Subsidiaries to, keep proper books, records and accounts, in which full and correct entries shall be made of all financial transactions and the assets and business of the Company and each of its Subsidiaries in accordance with generally accepted accounting principles. The Company shall, and shall cause its Subsidiaries to, permit the Blackstone Entities and their respective designated representatives, at reasonable times and upon reasonable prior notice to the Company, to review the books and records of the Company or any of such Subsidiaries and to discuss the affairs, finances and condition of the Company or any of such Subsidiaries with the officers of the Company or any such Subsidiary; provided, however, that the Company shall not be required to disclose any privileged information of the Company so long as the Company has used its best efforts to enter into an arrangement pursuant to which it may provide such information to the Blackstone Entities without the loss of any such privilege.

3.2 Periodic Reporting. (a) The Company will promptly deliver to each Blackstone Entity when available one copy of each annual report on Form 10-K and quarterly report on Form 10-Q of the Company, as filed with the SEC. In the event the Company is not required to file an annual report on Form 10-K or quarterly report on Form 10-Q, the Company may, in lieu of the requirements of the preceding sentence, deliver, or cause to be delivered, the following to each Blackstone Entity:

(i) as soon as available, but not later than ninety (90) days after the end of each fiscal year of the Company, a copy of the audited consolidated balance sheet of the Company and its Subsidiaries as of the end of such fiscal year and the related statements of operations and cash flows for such fiscal year, setting forth in each case in comparative form the figures for the previous year, all in reasonable detail;

(ii) commencing with the fiscal period ending after September 30, 2010, as soon as available, but in any event not later than forty five (45) days after the end of each of the first three fiscal quarters of each fiscal year, the unaudited consolidated balance sheet of the Company and its Subsidiaries, and the related statements of operations and cash flows for such quarter and for the period commencing on the first day of the fiscal year and ending on the last day of such quarter;

4

(b) The Company shall deliver or cause to be delivered to each Blackstone Entity:

(i) to the extent otherwise prepared by the Company, operating and capital expenditure budgets and periodic information packages relating to the operations and cash flows of the Company and its Subsidiaries; and

(ii) such other reports and information as may be reasonably requested by any Blackstone Entity; provided, however, that the Company shall not be required to disclose any privileged information of the Company so long as the Company has used its best efforts to enter into an arrangement pursuant to which it may provide such information to the Blackstone Entities without the loss of any such privilege.

ARTICLE IV. MISCELLANEOUS

4.1 Termination. This Agreement shall terminate at such time as Ensemble Parent is no longer entitled to designate a Director pursuant to Section 2.1(a).

4.2 Notices. Any notice, request, instruction or other document to be given hereunder by any party hereto to another party hereto shall be in writing, shall be and shall be deemed given when (a) delivered personally, (b) five (5) Business Days after being sent by certified or registered mail, postage prepaid, return receipt requested, (c) one (1) Business Day after being sent by Federal Express or other nationally recognized overnight courier, or (d) if transmitted by facsimile, if confirmed within 24 hours thereafter by a signed original sent in the manner provided in clause (a), (b) or (c) to the parties at the following addresses (or at such other address for a party as shall be specified by notice from such party):

if to the Company:

Team Health Holdings, Inc.

1900 Winston Road

Suite 300

Knoxville, Tennessee 37919

Attention: Lynn Massingale, M.D.

Fax: (865) 539-8030

if to Ensemble Parent:

c/o The Blackstone Group L.P.

345 Park Avenue, 31^st Floor

New York, New York 10154

Attention: Neil Simpkins

Fax: (212) 583-5257

4.3 Further Assurances. The parties hereto will use their best efforts to sign such further documents, cause such meetings to be held, resolutions passed, exercise their votes and do and perform and cause to be done such further acts and things as may be necessary in order to give full effect to this Agreement and every provision hereof.

4.4 Assignment. Neither the Company nor Ensemble Parent shall assign all or any part of this Agreement without the prior written consent of the other party; provided, however, that Ensemble Parent shall be entitled to assign, in whole or in part, to any of its Affiliates or its Permitted Assigns without such prior written consent. Except as otherwise provided herein, this Agreement will inure to the benefit of and be binding on the parties hereto and their respective successors and permitted assigns.

5

4.5 Amendment; Waiver. This Agreement may be amended, supplemented or otherwise modified only by a written instrument executed by the parties hereto. No waiver by any party of any of the provisions hereof will be effective unless explicitly set forth in writing and executed by the party so waiving. Except as provided in the preceding sentence, no action taken pursuant to this Agreement, including without limitation, any investigation by or on behalf of any party, will be deemed to constitute a waiver by the party taking such action of compliance with any covenants or agreements contained herein. The waiver by any party hereto of a breach of any provision of this Agreement will not operate or be construed as a waiver of any subsequent breach.

4.6 Third Parties. This Agreement does not create any rights, claims or benefits inuring to any Person that is not a party hereto nor create or establish any third party beneficiary hereto.

4.7 Governing Law. This Agreement will be governed by, and construed in accordance with, the laws of the State of Delaware.

4.8 Jurisdiction. The Court of Chancery of the State of Delaware and any state appellate court therefrom within the State of Delaware (or, if the Court of Chancery of the State of Delaware declines to accept jurisdiction over a particular matter, any state or federal court within the State of Delaware having jurisdiction) shall have exclusive jurisdiction over the parties with respect to any dispute or controversy between them arising under or in connection with this agreement and, by execution and delivery of this agreement, each of the parties to this Agreement submits to the exclusive jurisdiction of those courts, including but not limited to the in personam and subject matter jurisdiction of those courts, waives any objections to such jurisdiction on the grounds of venue or forum non conveniens, the absence of in personam or subject matter jurisdiction and any similar grounds, consents to service of process by mail (in accordance with the notice provisions of this Agreement) or any other manner permitted by Law, and irrevocably agrees to be bound by any judgment rendered thereby in connection with this Agreement.

4.9 MUTUAL WAIVER OF JURY TRIAL. THE PARTIES HERETO WAIVE ALL RIGHT TO TRIAL BY JURY IN ANY ACTION, SUIT OR PROCEEDING BROUGHT TO ENFORCE OR DEFEND ANY RIGHTS OR REMEDIES UNDER THIS AGREEMENT.

4.10 Specific Performance. Each of the parties hereto acknowledges and agrees that in the event of any breach of this Agreement by any of them, the non-breaching party would be irreparably harmed and could not be made whole by monetary damages. Each party accordingly agrees to waive the defense in any action for specific performance that a remedy at law would be adequate and that the parties, in addition to any other remedy to which they may be entitled at law or in equity, shall be entitled to compel specific performance of this Agreement.

4.11 Entire Agreement. This Agreement sets forth the entire understanding of the parties hereto with respect to the subject matter hereof. There are no agreements, representations, warranties, covenants or undertakings with respect to the subject matter hereof other than those expressly set forth herein. This Agreement supersedes all other prior agreements and understandings between the parties with respect to such subject matter.

4.12 Titles and Headings. The section headings contained in this Agreement are for reference purposes only and will not affect the meaning or interpretation of this Agreement.

6

4.13 Severability. If one or more of the provisions, paragraphs, words, clauses, phrases or sentences contained herein, or the application thereof in any circumstances, is held invalid, illegal or unenforceable in any respect for any reason, the validity, legality and enforceability of any such provision, paragraph, word, clause, phrase or sentence in every other respect and of the remaining provisions, paragraphs, words, clauses, phrases or sentences hereof shall not be in any way impaired, it being intended that all rights, powers and privileges of the parties hereto shall be enforceable to the fullest extent permitted by Law.

4.14 Counterparts. This Agreement may be executed in any number of counterparts, each of which will be deemed to be an original and all of which together will be deemed to be one and the same instrument.

4.15 Effectiveness. This Agreement shall become effective upon the Closing Date and prior thereto shall be of no force or effect.

7

IN WITNESS WHEREOF, each of the undersigned has executed this Agreement or caused this Agreement to be executed on its behalf as of the date first written above.