EXHIBIT 4.1 STOCKHOLDERS' AGREEMENT This Stockholders' Agreement (this "Agreement") is entered into as of January 7, 1999, by and among McLeodUSA Incorporated, a Delaware corporation (the "Company"); IES Investments Inc., an Iowa corporation ("IES"); Clark E. McLeod ("McLeod"); Mary E. McLeod (together with McLeod, the "McLeods"); Richard A. Lumpkin ("Lumpkin") and each of the former stockholders of Consolidated Communications Inc. ("CCI") and certain permitted transferees of the former CCI shareholders in each case who are listed in Schedule I hereto (the "CCI ---------- Shareholders"); and M/C Investors L.L.C. ("M/C Investors") and Media/Communications Partners III Limited Partnership, a Delaware limited partnership ("M/C Partners" and together with M/C Investors, the "New Stockholders"). IES, the McLeods, Lumpkin and the CCI Shareholders party hereto are referred to herein collectively as the "1998 Stockholders" and individually as a "1998 Stockholder." WHEREAS, the Company and the 1998 Stockholders are parties to a Stockholders' Agreement entered into as of November 18, 1998 (the "1998 Stockholders' Agreement"); WHEREAS, in order to induce the Company and Bravo Acquisition Corporation, a wholly owned subsidiary of the Company, to enter into an Agreement and Plan of Merger (the "Merger Agreement") to which the New Stockholders and certain others are a party, the New Stockholders, concurrent with the execution and delivery of the Merger Agreement, are entering into this Agreement; WHEREAS, upon the closing of the Merger Agreement and the transactions contemplated thereby, the New Stockholders will become stockholders of the Company; and WHEREAS, the Company, the 1998 Stockholders and the New Stockholders deem it to be in the best interests of the Company and its stockholders to enter into this Agreement to continue to provide for the continuity and stability of the business and policies of the Company on the terms and conditions hereinafter set forth; NOW, THEREFORE, for and in consideration of the foregoing and of the mutual covenants and agreements contained herein, the parties hereto agree as follows: 1. [INTENTIONALLY DELETED] 2. VOTING AGREEMENT 2.1 Board of Directors (i) For the period commencing on the Effective Date (as defined in Section 2.2) and ending on the Expiration Date (as defined in Section 2.2), each 1998 Stockholder, for so long as such 1998 Stockholder beneficially and continuously owns at least four million (4,000,000) shares of the Company's Class A common stock, $.01 par value per share (the "Class A Common Stock"), subject to adjustment pursuant to Section 5.1, shall take or cause to be taken all such action within their respective power and authority as may be required: (a) to cause to be elected to the Board of Directors of the Company (the "Board of Directors" or the "Board") one (1) director designated by the New Stockholders, for so long as the New Stockholders collectively beneficially and continuously own at least two million five hundred thousand (2,500,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1); (b) (b) to cause to be elected to the Board a director nominated by the Board to replace a director designated pursuant to paragraph (i)(a) above upon the earlier to occur of such designated director's resignation (and the acceptance of such resignation by the Board) and the expiration of such director's term as a result of the New Stockholders no longer collectively beneficially and continuously owning at least two million five hundred thousand (2,500,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1) at any time during the period commencing on the Effective Date and ending on the Expiration Date; it being understood that within three (3) business days following such time as the New Stockholders no longer collectively beneficially and continuously own at least two million five hundred thousand (2,500,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1) at any time during such period, the New Stockholders shall use their best efforts to cause the director designated by the New Stockholders to tender its immediate resignation to the Board which the Board may accept or, if consented to by such director, reject; -2- (c) to establish and maintain the authorized size of the Board at up to eleven (11) directors; and (d) to cause to be elected to the Board, if and as nominated by the Board, up to five (5) non-employee directors. (ii) For the period commencing on the Effective Date and ending on the Expiration Date, the New Stockholders, for so long as the New Stockholders collectively beneficially and continuously own at least two million five hundred thousand (2,500,000) shares of Class A Common Stock, subject to adjustment pursuant to Section 5.1, shall take or cause to be taken all such action within their respective power and authority as may be required: (a) to establish and maintain the authorized size of the Board of Directors at up to eleven (11) directors; (b) to cause to be elected to the Board one (1) director designated by IES, for so long as IES beneficially and continuously owns at least four million (4,000,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1); (c) to cause Lumpkin to be elected to the Board, for so long as Lumpkin and the CCI Shareholders collectively beneficially and continuously own at least four million (4,000,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1); (d) to cause to be elected to the Board three (3) directors who are executive officers of the Company designated by McLeod, for so long as the McLeods collectively beneficially and continuously own at least four million (4,000,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1); (e) to cause to be elected to the Board one (1) director designated by the New Stockholders, for so long as the New Stockholders collectively beneficially and continuously own at least two million five hundred thousand (2,500,000) shares of Class A Common Stock (subject to adjustment pursuant to Section 5.1); (f) to cause to be elected to the Board a director or directors nominated by the Board to replace a director or directors designated pursuant to paragraphs (ii)(b) through (ii)(e) above upon the earlier to occur of such designated -3- director's or directors' resignation (and the acceptance of such resignation by the Board) and the expiration of such director's or directors' term as a result of any party or parties identified in paragraphs (ii)(b) through (ii)(e) above no longer beneficially owning the specified number of shares of Class A Common Stock as set forth in paragraphs (ii)(b) through (ii)(e), as the case may be, at any time during the period commencing on the Effective Date and ending on the Expiration Date; it being understood that within three (3) business days following such time as the party or parties identified in paragraphs (ii)(b) through (ii)(e) above no longer beneficially and continuously own the specified number of shares of Class A Common Stock as set forth in paragraphs (ii)(b) through (ii)(e), as the case may be, during such period, such party or parties shall use its or their respective best efforts to cause the director or directors designated by such party or parties to tender their immediate resignation to the Board which the Board may accept or reject; and (g) to cause to be elected to the Board, if and as nominated by the Board, up to five (5) non-employee directors. For purposes of this Section 2.1, (i) the New Stockholders shall be deemed to be a single stockholder of the Company, and a New Stockholder shall be deemed to own shares "continuously" as long as the shares of such New Stockholder are owned by such New Stockholder or a New Stockholder Permitted Transferee (as defined in Section 3.1) and (ii) Lumpkin and all of the CCI Shareholders shall be deemed to be a single stockholder of the Company, and a CCI Shareholder shall be deemed to own shares "continuously" as long as the shares of such CCI Shareholder are owned by such CCI Shareholder or a CCI Permitted Transferee (as defined in the 1998 Stockholders' Agreement). 2.2 Definitions For purposes of this Agreement, the following terms have the meanings indicated: (a) "Affiliate" and "Associate" shall have the respective meanings ascribed to such terms in Rule 12b-2 under the Securities Exchange Act of 1934, as amended (the "Exchange Act"). (b) A person shall be deemed the "Beneficial Owner" of and shall be deemed to "beneficially own" any securities: -4- (i) which such person or any of such person's Affiliates or Associates, directly or indirectly, has the right to acquire (whether such right is exercisable immediately or only after the passage of time) pursuant to any agreement, arrangement or understanding (whether or not in writing), or upon the exercise of conversion rights, exchange rights, other rights, warrants or options, or otherwise; (ii) which such person or any of such person's Affiliates or Associates, directly or indirectly, has the right to vote or dispose of or has "beneficial ownership" of (as determined pursuant to Rule 13d-3 under the Exchange Act), including pursuant to any agreement, arrangement or understanding, whether or not in writing; or (iii) which are beneficially owned, directly or indirectly, by any other person (or any Affiliate or Associate thereof) with which such person or any of such person's Affiliates or Associates has any agreement, arrangement or understanding (whether or not in writing), for the purpose of acquiring, holding, voting or disposing of any voting securities of the Company. For purposes of the definition of "Beneficial Owner" and "beneficially own," the terms "agreement," "arrangement" and "understanding" shall not include this Agreement, the 1998 Stockholders' Agreement or the Stockholders' Agreement, dated as of June 14, 1997, as amended on September 19, 1997 (the "1997 Stockholders' Agreement"). (c) "Effective Date" shall mean the date on which the Merger (as defined in the Merger Agreement) is consummated in accordance with the terms and conditions of the Merger Agreement. (d) "Expiration Date" shall mean December 31, 2001. 3. TRANSFERS OF SECURITIES 3.1 Restrictions on Transfers (a) Except as otherwise provided in this Section 3.1 or Section 3.2, the New Stockholders hereby agree that until the Expiration Date, the New -5- Stockholders will not offer, sell, contract to sell, grant any option to purchase, or otherwise dispose of, directly or indirectly, ("Transfer"), any equity securities of the Company or any other securities convertible into or exercisable for such equity securities ("Securities") beneficially owned by such New Stockholders as a result of the Merger (including distributions of Securities with respect to such Securities and Securities acquired as a result of a stock split with respect to such Securities) without submitting a written request to, and receiving the prior written consent of, the Board of Directors; provided, however, that a New Stockholder may transfer Securities to any - -------- ------- beneficial owner or Affiliate of such New Stockholder, in each case provided that (i) such transfer is done in accordance with the transfer restrictions applicable to such Securities under federal and state securities laws and (ii) the transferee agrees to be bound by the terms hereof as a New Stockholder with respect to the shares being transferred pursuant to this Section (any such New Stockholder transferee pursuant to this proviso, a "New Stockholder Permitted Transferee"), and any such transfer shall not constitute a "Transfer" for purposes of this Agreement. Notwithstanding the foregoing, no party hereto shall avoid the provisions of this Agreement by making one or more transfers to one or more New Stockholder Permitted Transferees and then disposing of all or any portion of such party's interest in any such New Stockholder Permitted Transferee. In the event that the Board of Directors consents to any Transfer of Securities by a Principal Stockholder (for purposes of this Agreement, the term "Principal Stockholder" shall have the same meaning as ascribed to such term in the 1998 Stockholders' Agreement) pursuant to the written request of such Principal Stockholder (the "Transferring Principal Stockholder") during the period commencing on January 1, 2000 and ending on the Expiration Date and except as otherwise provided in Section 3.1(b) and Section 3.2, the New Stockholders shall notwithstanding the provisions of this Section 3.1(a), have the right to Transfer a percentage of the total number of Securities beneficially owned by the New Stockholders equal to the percentage of the total number of Securities beneficially owned by the Transferring Principal Stockholder that the Board of Directors has consented may be Transferred by such Transferring Principal Stockholder. In the event the Board of Directors consents to any Transfer of Securities by the New Stockholders pursuant to the written request of the New Stockholders (the "Transferring New Stockholders"), and except as otherwise provided in Section 3.1(b) and Section 3.2 of the 1998 Stockholders' Agreement, each Principal Stockholder shall, notwithstanding the provisions of Section 3.1(a) of the 1998 Stockholders' Agreement, have the right to Transfer a percentage of the total number of Securities beneficially owned by such Principal Stockholder equal to the percentage of the total number of Securities beneficially owned by the Transferring New Stockholders that the Board of Directors has consented may be Transferred by such Transferring New Stockholders. (b) In addition to the provisions of Section 3.1(a), for the period commencing for the quarter ending December 31, 1999 and ending on the Expiration Date, the Board shall determine prior to the public release of the -6- Company's consolidated financial results with respect to each such financial reporting quarter during such period, the aggregate number, if any, of shares of Class A Common Stock (not to exceed in the aggregate fifty thousand (50,000) shares of Class A Common Stock per quarter, subject to adjustment pursuant to Section 5.1) that may be Transferred by the New Stockholders (the "Transfer Amount") during the period commencing on the third (3rd) business day and ending on the twenty-third (23rd) business day following such public release of the Company's quarterly or annual financial results or such other trading period designated or permitted by the Board with respect to the purchase and sale of its Securities (each such period, a "Transfer Period"). Notwithstanding the provisions of Section 3.1(a), the New Stockholders shall be entitled to Transfer during each Transfer Period, provided such Transfer is effected in accordance with all applicable federal and state securities laws, a number of shares of Class A Common Stock equal to the Transfer Amount, if any, for such Transfer Period. In no event shall any portion of a Transfer Amount that is not utilized by the New Stockholders during a Transfer Period be reallocated or otherwise credited to any subsequent Transfer Periods. Notwithstanding the foregoing provisions of this Section 3.1(b), to the extent that the Company permits the Principal Stockholders the opportunity to Transfer shares of Class A Common Stock pursuant to Section 3.1(b) of the 1998 Stockholders' Agreement during the period commencing on January 1, 2000 and ending on the Expiration Date, the Company shall grant the New Stockholders the opportunity to Transfer on the same terms and conditions a number of shares of Class A Common Stock equal to the number of shares which each Principal Stockholder is entitled to Transfer pursuant to such Section 3.1(b), without considering those provisions of Section 3.1(b) of the 1998 Stockholders' Agreement relating to the reallocation of amounts among the Principal Stockholders. To the extent the Board determines a Transfer Amount with respect to the New Stockholders for any particular quarter, the Board shall determine an equal Transfer Amount for such quarter with respect to each Principal Stockholder pursuant to Section 3.1(b) of the 1998 Stockholders' Agreement. (c) For the period commencing for the quarter ending December 31, 1999 and ending on the Expiration Date, the Company shall give the New Stockholders prompt written notice (in any event no later than fifty (50) days prior to the beginning of the applicable Transfer Period) of its determination of any Transfer Amount. Within seven (7) days of receipt of such notice, the New Stockholders shall provide written notice to the Company of the number of shares of Class A Common Stock that the New Stockholders desire to Transfer pursuant to Section 3.1(b). (d) During the year ending December 31, 1999, to the extent the Company participates in a strategic transaction with an outside investor(s) pursuant to which such investor(s) acquires Securities of the Company at a premium to the then average trading price of the Company's Securities, and after the Company has been paid or otherwise received its consideration or proceeds from -7- such transaction as determined by the Company, the Principal Stockholders and the New Stockholders may be entitled to participate in such transaction on a pro rata basis as determined by the Board of Directors. (e) For purposes of this Section 3.1, the New Stockholders shall be deemed to be a single stockholder of the Company, and Lumpkin and all of the CCI Shareholders shall be deemed to be a single Principal Stockholder. 3.2 Registration Rights (a) In the event that the Board of Directors consents pursuant to Section 3.1(a) of the 1998 Stockholders' Agreement to a Principal Stockholder's request for a Transfer during the period commencing on January 1, 2000 and ending on the Expiration Date and in connection therewith, the Company agrees to register Securities with respect to such Transfer under the Securities Act of 1933, as amended (the "Securities Act"), the Company shall grant the New Stockholders the opportunity (subject to reduction in the event the registered Transfer is underwritten) to register for Transfer under the Securities Act a percentage of the total number of Securities beneficially owned by the New Stockholders equal to the percentage of the total number of Securities beneficially owned by the Transferring Principal Stockholder that such Transferring Principal Stockholder is registering for Transfer under the Securities Act, on the same terms and conditions as the Transferring Principal Stockholder. In the event that the Board of Directors consents pursuant to Section 3.1(a) of this Agreement to the New Stockholders' request for a Transfer, and in connection therewith the Company agrees to register Securities with respect to such Transfer under the Securities Act, the Company shall grant each Principal Stockholder pursuant to Section 3.1(a) of the 1998 Stockholders' Agreement the opportunity (subject to reduction in the event the registered Transfer is underwritten) to register for Transfer under the Securities Act a percentage of the total number of Securities beneficially owned by such Principal Stockholder equal to the percentage of the total number of Securities beneficially owned by the Transferring New Stockholders that such Transferring New Stockholders are registering under the Securities Act, on the same terms and conditions as the Transferring New Stockholders. (b) To the extent that the Company grants pursuant to Section 3.1(b) of the 1998 Stockholders' Agreement a Principal Stockholder the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act during the period commencing on January 1, 2000 and ending on the Expiration Date, the Company shall grant the New Stockholders the opportunity (subject to reduction in the event the registered Transfer is underwritten) to register an equal number of shares of Class A Common Stock for Transfer under the Securities Act on the same terms and conditions, without considering those provisions of Section 3.1(b) of the 1998 Stockholders' Agreement relating to the reallocation of amounts among the Principal Stockholders. To the extent that the Company grants pursuant -8- to Section 3.1(b) of this Agreement the New Stockholders the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act, the Company shall grant each Principal Stockholder pursuant to Section 3.1(b) of the 1998 Stockholders' Agreement the opportunity (subject to reduction in the event the registered Transfer is underwritten) to register an equal number of shares of Class A Common Stock for Transfer under the Securities Act on the same terms and conditions. (c) For the period commencing on January 1, 2000 and ending on the Expiration Date, in the event the Company proposes to register any shares of Class A Common Stock under the Securities Act pursuant to an underwritten primary offering (other than pursuant to a registration statement on Form S-4 or Form S-8 or any successor forms thereto or other form which would not permit the inclusion of the shares of Class A Common Stock of the New Stockholders), the Company, as determined by the Board of Directors, shall give written notice to the New Stockholders of its intention to effect such a registration. Following any such notice, the Board of Directors shall undertake to determine the aggregate number, if any, of shares of Class A Common Stock held by the New Stockholders (not to exceed in the aggregate on a per year basis a number of shares of Class A Common Stock equal to fifteen percent (15%) of the total number of shares of Class A Common Stock beneficially owned by the New Stockholders as of the Effective Date) to be registered by the Company under the Securities Act (the "Registrable Amount") for Transfer by the New Stockholders in connection with such offering during such period. If the Board determines to register shares of Class A Common Stock held by the New Stockholders pursuant to this Section 3.2(c), the Company will promptly give written notice of such determination to the New Stockholders, and thereupon the Company will use commercially reasonable efforts to effect the registration of that portion of the Registrable Amount that the New Stockholders indicate a desire to register. All terms, conditions and rights with respect to such registration (including but not limited to any determination to reduce the Registrable Amount) shall be determined by the Board, provided that (i) the representations and warranties of the New Stockholders shall be customary taking into account, among other things, the nature of the offering and the New Stockholders' relationship with the Company, and (ii) the Company shall be responsible for all expenses with respect to such registration other than underwriting discounts and commissions allocable to the Class A Common Stock of the New Stockholders, which underwriting discounts and commissions shall be the responsibility of the New Stockholders. Notwithstanding the foregoing provisions of this Section 3.2(c), to the extent that the Company grants pursuant to Section 3.2(c) of the 1998 Stockholders' Agreement the Principal Stockholders the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act during the period commencing on January 1, 2000 and ending on the Expiration Date, the Company shall grant the New Stockholders the opportunity to register shares of Class A Common Stock on a substantially similar basis. To the extent that the Company grants pursuant to Section 3.2(c) of this Agreement the New -9- Stockholders the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act, the Company shall grant each Principal Stockholder pursuant to Section 3.2(c) of the 1998 Stockholders' Agreement the opportunity to register shares of Class A Common Stock on a substantially similar basis. (d) In addition to the registration rights granted pursuant to Sections 3.2(a), (b) and (c), no more frequently than once during each of the calendar years ending December 31, 2000 and 2001 (each such year, an "Annual Period"), and upon either (i) the receipt of a written request of the New Stockholders or (ii) a determination by the Board of Directors, the Board shall undertake to determine the Registrable Amount, if any, for Transfer by the New Stockholders. If the Board determines to register shares of Class A Common Stock held by the New Stockholders pursuant to this Section 3.2(d), the Company will promptly give written notice of such determination to the New Stockholders, and thereupon the Company will use commercially reasonable efforts to effect the registration of that portion of the Registrable Amount that the New Stockholders indicate a desire to register. All terms, conditions and rights with respect to such registration (including but not limited to any determination to reduce the Registrable Amount) shall be determined by the Board, provided that (i) the representations and warranties of the New Stockholders shall be customary taking into account, among other things, the nature of the offering and the New Stockholders' relationship with the Company, and (ii) the Company shall be responsible for all expenses with respect to such registration other than underwriting discounts and commissions allocable to the Class A Common Stock of the New Stockholders, which underwriting discounts and commissions shall be the responsibility of the New Stockholders. Notwithstanding the foregoing provisions of this Section 3.2(d), to the extent that the Company grants pursuant to Section 3.2(d) of the 1998 Stockholders' Agreement the Principal Stockholders the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act during the period commencing on January 1, 2000 and ending on the Expiration Date, the Company shall grant the New Stockholders the opportunity to register shares of Class A Common Stock on a substantially similar basis. To the extent that the Company grants pursuant to Section 3.2(d) of this Agreement the New Stockholders the opportunity to register shares of Class A Common Stock for Transfer under the Securities Act, the Company shall grant each Principal Stockholder pursuant to Section 3.2(d) of the 1998 Stockholders' Agreement the opportunity to register shares of Class A Common Stock on a substantially similar basis. (e) For purposes of this Section 3.2, the New Stockholders shall be deemed to be a single stockholder of the Company, and Lumpkin and all of the CCI Shareholders shall be deemed to be a single Principal Stockholder. (f) Notwithstanding any other provision of this Agreement, to the extent the Company has undertaken to register Securities of the New Stockholders -10- pursuant to this Section 3.2, the Company may subsequently determine not to register such Securities and may either not file a registration statement or otherwise withdraw or abandon a registration statement previously filed with respect to the registration of such Securities; provided that to the extent the Principal Stockholders are also participating in such registration, the New Stockholders and the Principal Stockholders will be treated on a substantially similar basis with respect to any such determination not to register Securities or the withdrawal or abandonment of a registration statement previously filed as contemplated by this Section 3.2(f). 4. REPRESENTATIONS AND WARRANTIES 4.1 Representations and Warranties of Non-individual Stockholders Each non-individual party to this Agreement hereby represents and warrants, as of the date of this Agreement, to the Company and to each other party as follows: 4.1.1 Authorization Such party has taken all action necessary for it to enter into this Agreement and to consummate the transactions contemplated hereby. 4.1.2 Binding Obligation This Agreement constitutes a valid and binding obligation of such party, enforceable in accordance with its terms, except to the extent that such enforceability may be limited by bankruptcy, insolvency, and similar laws affecting the rights and remedies of creditors generally, and by general principles of equity and public policy; and each document and instrument to be executed by such party pursuant hereto, when executed and delivered in accordance with the provisions hereof, shall be a valid and binding obligation of such party, enforceable in accordance with its terms (with the aforesaid exceptions). 4.2 Representations and Warranties of Individual Stockholders Each party to this Agreement who is an individual hereby represents and warrants, as of the date of this Agreement, to the Company and to each other party as follows: -11- 4.2.1 Power and Authority Such party has the legal capacity and all other power and authority necessary to enter into this Agreement and to consummate the transactions contemplated hereby. 4.2.2 Binding Obligation This Agreement constitutes a valid and binding obligation of such party, enforceable in accordance with its terms, except to the extent that such enforceability may be limited by bankruptcy, insolvency, and similar laws affecting the rights and remedies of creditors generally, and by general principles of equity and public policy; and each document and instrument to be executed by such party pursuant hereto, when executed and delivered in accordance with the provisions hereof, shall be a valid and binding obligation of such party, enforceable in accordance with its terms (with the aforesaid exceptions). 4.3 Representations and Warranties of the Company The Company hereby represents and warrants, as of the date of this Agreement, to each party as follows: 4.3.1 Authorization The Company has taken all corporate action necessary for it to enter into this Agreement and to consummate the transactions contemplated hereby. 4.3.2 Binding Obligation This Agreement constitutes a valid and binding obligation of the Company, enforceable in accordance with its terms, except to the extent that such enforceability may be limited by bankruptcy, insolvency, and similar laws affecting the rights and remedies of creditors generally, and by general principles of equity and public policy; and each document and instrument to be executed by the Company pursuant hereto, when executed and delivered in accordance with the provisions hereof, shall be a valid and binding obligation of the Company, enforceable in accordance with its terms (with the aforesaid exceptions). 5. MISCELLANEOUS 5.1 Effect of Changes in Capitalization All share amounts of the Company's capital stock referred to in this Agreement shall be appropriately and proportionally adjusted for any recapitalization, reclassification, stock split-up, combination of shares, exchange of -12- shares, stock dividend or other distribution payable in capital stock, or other increase or decrease in such shares effected without receipt of consideration by the Company, occurring after the date of this Agreement. 5.2 Additional Actions and Documents Each of the parties hereto hereby agrees to take or cause to be taken such further actions, to execute, deliver and file or cause to be executed, delivered and filed such further documents and instruments, and to obtain such consents, as may be necessary or as may be reasonably requested in order to fully effectuate the purposes, terms and conditions of this Agreement, whether before, at or after the Effective Date. 5.3 Entire Agreement; Amendment This Agreement constitutes the entire agreement among the parties hereto as of the date hereof with respect to the specific matters contemplated herein (except with respect to the 1998 Stockholders, as set forth in the 1998 Stockholders' Agreement and the 1997 Stockholders' Agreement). No amendment, modification or discharge of this Agreement shall be valid or binding unless set forth in writing and duly executed by the Company and by the party against whom enforcement of the amendment, modification or discharge is sought. Any amendment, modification or discharge of this Agreement to be enforced against the New Stockholders shall be valid and binding with respect to all New Stockholders if such amendment, modification or discharge is executed by those New Stockholders holding a majority of the shares of Class A Common Stock issued to the New Stockholders in the Merger (including distributions of Securities with respect to such Securities and Securities acquired as a result of a stock split with respect to such Securities). 5.4 Limitation on Benefit; Parties It is the explicit intention of the parties hereto that no person or entity other than the parties hereto is or shall be entitled to bring any action to enforce any provision of this Agreement against any of the parties hereto, and the covenants, undertakings and agreements set forth in this Agreement shall be solely for the benefit of, and shall be enforceable only by, the parties hereto or their respective successors, heirs, executors, administrators, legal representatives and permitted assigns. For purposes of this Agreement and notwithstanding any other provision hereof, a "party" to or of this Agreement shall be deemed to mean only those individuals or entities that have executed and delivered this Agreement. -13- 5.5 Binding Effect; Specific Performance This Agreement shall be binding upon and shall inure to the benefit of the parties hereto and their respective successors, heirs, executors, administrators, legal representatives and permitted assigns. No party shall assign this Agreement without the written consent of the other parties hereto; and such consent shall not be unreasonably withheld. The parties hereto agree that irreparable damage would occur in the event any provision of this Agreement was not performed in accordance with the terms hereof and that the parties shall be entitled to specific performance of the terms hereof, in addition to any other remedy at law or in equity. 5.6 Governing Law This Agreement, the rights and obligations of the parties hereto, and any claims or disputes relating thereto, shall be governed by and construed in accordance with the laws of Delaware (excluding the choice of law rules thereof). 5.7 Notices All notices, demands, requests, or other communications which may be or are required to be given, served, or sent by any party to any other party pursuant to this Agreement shall be in writing and shall be hand-delivered or mailed by first-class, registered or certified mail, return receipt requested, postage prepaid, or transmitted by telegram, telecopy, facsimile transmission or telex, addressed as follows: (i) If to the Company or to the McLeods: McLeodUSA Incorporated McLeodUSA Technology Park 6400 C Street, SW, P.O. Box 3177 Cedar Rapids, IA 52406-3177 Attention: Randall Rings Facsimile: (319) 298-7901 (ii) If to IES: IES Investments Inc. 200 1st Street SE Cedar Rapids, IA 52401 Attention: James E. Hoffman Facsimile: (319) 398-4204 -14- (iii) If to Lumpkin or any CCI Shareholder: P.O. Box 1234 Mattoon, IL 61938 Attention: Richard A. Lumpkin Facsimile: (217) 234-9934 with a copy to : Schiff Hardin & Waite 6600 Sears Tower Chicago, Illinois 60606 Attention: David R. Hodgman, Esq. Facsimile: (312) 258-5600 (iv) If to the New Stockholders: c/o Media/Communications Partners III Limited Partnership 75 State Street Boston, Massachusetts 02109 Attention: James F. Wade Facsimile: (617) 345-7201 with a copy to: Edwards & Angell, LLP 101 Federal Street Boston, MA 02110 Attention: Stephen O. Meredith, Esq. Facsimile: (617) 439-4170 Each party may designate by notice in writing a new address to which any notice, demand, request or communication may thereafter be so given, served or sent. Each notice, demand, request or communication which shall be hand- delivered, mailed, transmitted, telecopied or telexed in the manner described above, or which shall be delivered to a telegraph company, shall be deemed sufficiently given, served, sent, received or delivered for all purposes at such time as it is delivered to the addressee (with the return receipt, the delivery receipt, or the answerback being deemed conclusive, but not exclusive, evidence of such delivery) or at such time as delivery is refused by the addressee upon presentation. 5.8 Termination (a) This Agreement shall terminate and be of no further force or effect as to a 1998 Stockholder (and not as to the Company and the New -15- Stockholders) at such time as the 1998 Stockholders' Agreement shall terminate and be of no further force or effect with respect to such 1998 Stockholder. (b) If (i) during any Annual Period the Board of Directors has not provided the New Stockholders a reasonable opportunity to Transfer shares of Class A Common Stock pursuant to the registration of such shares under the Securities Act pursuant to Section 3.2 in an aggregate amount equal to not less than fifteen percent (15%) of the total number of shares of Class A Common Stock beneficially owned by the New Stockholders as of the Effective Date or (ii) after January 1, 2000, the 1998 Stockholders' Agreement has been terminated by all parties thereto, then the New Stockholders may terminate this Agreement by providing written notice of termination to all other parties (x) in the case of clause (b)(i) above, no later than thirty (30) days following the end of such Annual Period and (y) in the case of cause (b)(ii) above, at any time after January 1, 2000, such that all rights and obligations hereunder shall cease, and this Agreement shall be of no further force or effect. (c) Unless otherwise previously terminated by the New Stockholders pursuant to Section 5.8(b), this Agreement shall terminate on the earlier to occur of (i) the termination of the Merger Agreement in accordance with the terms thereof and (ii) the Expiration Date. (d) For purposes of this Section 5.8, the New Stockholders shall be deemed to be a single stockholder of the Company, and Lumpkin and all of the CCI Shareholders shall be deemed to be a single stockholder of the Company. 5.9 Publicity The New Stockholders will use their reasonable best efforts to consult with the Company prior to issuing any press release, making any filing with any governmental entity or national securities exchange or making any other public dissemination of information by the New Stockholders within which this Agreement or the contents hereof are referenced or described. 5.10 Appointment of Representative (a) Each of the New Stockholders hereby appoints Media/Communications Partners III Limited Partnership, with power of substitution, as its exclusive agent to act on its behalf with respect to any and all actions to be taken under or amendments or modifications to be made to this Agreement (the "M/C Representative"). The M/C Representative shall take, and the New Stockholders agree that the M/C Representative shall take, any and all actions which the M/C Representative believes are necessary or advisable under this Agreement for and on behalf of each of the New Stockholders, as fully as if each of -16- the New Stockholders was acting on its own behalf, including, without limitation, dealing with the Company and the other parties hereto with respect to all matters arising under this Agreement, entering into any amendment or modification to this Agreement deemed advisable by the M/C Representative and taking any and all other actions specified in or contemplated by this Agreement. The Company and the other parties hereto shall have the right to rely upon all actions taken or not taken by the M/C Representative pursuant to this Agreement, all of which actions or omissions shall be legally binding upon each of the New Stockholders. (b) Each of the CCI Shareholders hereby appoints Lumpkin, with power of substitution, as its exclusive agent to act on its behalf with respect to any and all actions to be taken under or amendments or modifications to be made to this Agreement (the "CCI Representative"). The CCI Representative shall take, and the CCI Shareholders agree that the CCI Representative shall take, any and all actions which the CCI Representative believes are necessary or advisable under this Agreement for and on behalf of each of the CCI Shareholders, as fully as if each of the CCI Shareholders was acting on its own behalf, including, without limitation, dealing with the Company and the other parties hereto with respect to all matters arising under this Agreement, entering into any amendment or modification to this Agreement deemed advisable by the CCI Representative and taking any and all other actions specified in or contemplated by this Agreement. The Company and the other parties hereto shall have the right to rely upon all actions taken or not taken by the CCI Representative pursuant to this Agreement, all of which actions or omissions shall be legally binding upon each of the CCI Shareholders. 5.11 Execution in Counterparts To facilitate execution, this Agreement may be executed in as many counterparts as may be required; and it shall not be necessary that the signatures of, or on behalf of, each party, or that the signatures of all persons required to bind any party, appear on each counterpart; but it shall be sufficient that the signature of, or on behalf of, each party, or that the signatures of the persons required to bind any party, appear on one or more of the counterparts. All counterparts shall collectively constitute a single agreement. It shall not be necessary in making proof of this Agreement to produce or account for more than a number of counterparts containing the respective signatures of, or on behalf of, all of the parties hereto. It is the express understanding of the parties hereto that this Agreement shall be binding and enforceable with respect to the parties hereto on the terms herein set forth even if one or more of the CCI Shareholders do not sign this Agreement. -17- IN WITNESS WHEREOF, the undersigned have duly executed and delivered this Stockholders' Agreement, or have caused this Stockholders' Agreement to be duly executed and delivered on their behalf, as of the day and year first hereinabove set forth. MCLEODUSA INCORPORATED By: /s/ J. Lyle Patrick --------------------- Name: J. Lyle Patrick Title: Group Vice President, Chief Financial Officer and Treasurer M/C INVESTORS L.L.C. By: /s/ James F. Wade ------------------- Name: James F. Wade Title: MEDIA/COMMUNICATIONS PARTNERS III LIMITED PARTNERSHIP By: M/C III L.L.C., its General Partner By: /s/ James F. Wade ------------------- Name: James F. Wade Title: /s/ Clark E. McLeod /s/ Mary E. McLeod ----------------------- ---------------------- Clark E. McLeod Mary E. McLeod -18- /s/ Richard A. Lumpkin /s/ Gail G. Lumpkin ----------------------- ---------------------- Richard A. Lumpkin Gail G. Lumpkin IES INVESTMENTS INC. By: /s/ James E. Hoffman --------------------- Name: James E. Hoffman Title: President Margaret Lumpkin Keon Trust Mary Lee Sparks Trust dated May 13, 1978 dated May 13, 1978 - --------------------------------- --------------------------- Margaret Lumpkin Keon, as Trustee Mary Lee Sparks, as Trustee ----------------------------- Steven L. Grissom, as Trustee - --------------------------------- Mary Lee Sparks -19- The twelve trusts created under the Mary Green Lumpkin Gallo Trust Agreement dated December 29, 1989 one for the benefit of each of: Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks Bank One, Texas, N.A., Trustee - ------------------------------ By: --------------------------- The twelve trusts created under the Richard Adamson Lumpkin Grandchildren's Trust dated September 5, 1980, one for the benefit of each of: Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks Bank One, Texas, N.A., Trustee - ------------------------------ By: --------------------------- -20- The three trusts established by Richard Adamson Lumpkin under Trust Agreement dated February 6, 1970, one for the benefit of each of: Richard Anthony Lumpkin, Margaret Anne Keon, and Mary Lee Sparks Bank One, Texas, N.A., Trustee - ------------------------------ By: --------------------------- The twelve 1990 Personal Income Trusts established by Margaret L. Keon, Mary Lee Sparks, and Richard A. Lumpkin, each dated April 20, 1990, one for the benefit of each of: Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks - ----------------------------- David R. Hodgman, Trustee - ----------------------------- Steven L. Grissom, Trustee -21- SCHEDULE I Gail G. Lumpkin Margaret Lumpkin Keon, as Trustee under the Margaret Lumpkin Keon Trust dated May 13, 1978 Mary Lee Sparks and Steven L. Grissom, as Trustees of the Mary Lee Sparks Trust dated May 13, 1978 Bank One, Texas, N.A., as Trustee of the twelve trusts created under the Mary Green Lumpkin Gallo Trust Agreement dated December 29, 1989, one for the benefit of each of Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks Bank One, Texas, N.A., as Trustee of the twelve trusts created under the Richard Adamson Lumpkin Grandchildren's Trust dated September 5, 1980, one for the benefit of each of Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks Bank One, Texas, N.A., as Trustee of the three trusts established by Richard Adamson Lumpkin under the Trust Agreement dated February 6, 1970, one for the benefit of each of Richard Anthony Lumpkin, Margaret Anne Keon, and Mary Lee Sparks David R. Hodgman and Steven L. Grissom, as Trustees of the twelve 1990 Personal Income Trusts established by Margaret L. Keon, Mary Lee Sparks, and Richard A. Lumpkin, each dated April 20, 1990, one for the benefit of each of Joseph John Keon III, Katherine Stoddert Keon, Lisa Anne Keon, Margaret Lynley Keon, Pamela Keon Vitale, Susan Tamara Keon DeWyngaert, Benjamin Iverson Lumpkin, Elizabeth Arabella Lumpkin, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John Woodruff Sparks -22-