Exhibit 4.12 STOCKHOLDERS' AGREEMENT This Stockholders' Agreement (this "Agreement") is entered into as of June 14, 1997, and will be effective as of the date the Merger (as defined below) is consummated (the "Effective Date") by and among McLeodUSA Incorporated, a Delaware corporation (the "Company"); IES Investments Inc., an Iowa corporation ("IES"); Midwest Capital Group, Inc. ("MCG"); MWR Investments Inc. ("MWR"); Clark E. McLeod ("McLeod"); Mary E. McLeod (collectively with McLeod, the "McLeods"); and Richard A. Lumpkin ("Lumpkin") on behalf of each of the shareholders of Consolidated Communications Inc. ("CCI") listed in Schedule I hereto (the "CCI Shareholders"). IES, MCG, MWR, and the McLeods are - ---------- referred to herein collectively as the "Original Principal Stockholders" and individually as an "Original Principal Stockholder" and IES, MCG, MWR, the McLeods, Lumpkin and the CCI Shareholders are referred to herein collectively as the "Principal Stockholders" and individually as a "Principal Stockholder." WHEREAS, the Original Principal Stockholders and certain other stockholders of the Company are parties to a certain Investor Agreement, dated as of April 1, 1996 (the "Original Investor Agreement"), as amended by Amendment No. 1 to Investor Agreement among the Original Principal Stockholders dated October 23, 1996 (the "Amendment," and together with the Original Investor Agreement, the "Investor Agreement"); WHEREAS, upon consummation of the merger of CCI with and into Eastside Acquisition Co., a newly formed Delaware corporation and a wholly owned subsidiary of the Company (the "Merger"), Lumpkin and the CCI Shareholders will become stockholders of the Company and the Principal Stockholders desire to enter into this Agreement to set forth certain arrangements among the Principal Stockholders; WHEREAS, the Company and the Original Principal Stockholders intend that, as among them, this Agreement will supersede and replace the agreements contained in Section 1, Section 2, Section 3, Section 7 and Section 8 of the Original Investor Agreement as amended by the Amendment, as those sections apply to the Company and the Original Principal Stockholders. 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. VOTING AGREEMENT 1.1 Board of Directors For a period of three years commencing on the Effective Date, each Original Principal Stockholder, for so long as such Original Principal Stockholder beneficially owns at least 10% of the outstanding Class A common stock, $.01 par value per share, of the Company (the "Class A Common Stock"), determined on a fully diluted basis (that is, all outstanding Class A Common Stock and all outstanding options and other securities convertible into, or exercisable for, Class A Common Stock), and Lumpkin and the CCI Shareholders, for so long as they collectively beneficially own at least 10% of the outstanding Class A Common Stock (determined on a fully diluted basis), 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 of the Company (the "Board") up to eleven directors; (b) to cause to be elected to the Board one director designated by IES, subject to the provisions of Section 1.2, for so long as IES beneficially owns at least 10% of the outstanding Class A Common Stock (determined on a fully diluted basis); (c) to cause to be elected to the Board one director designated by MWR, subject to the provisions of Section 1.2, for so long as MWR beneficially owns at least 10% of the outstanding Class A Common Stock (determined on a fully diluted basis); (d) to cause Lumpkin to be elected to the Board, for so long as Lumpkin and the CCI Shareholders collectively beneficially own at least 10% of the outstanding Class A Common Stock (determined on a fully diluted basis); (e) to cause to be elected to the Board three directors who are executive officers of the Company designated by McLeod, for so long as the McLeods collectively beneficially own at least 10% of the outstanding Class A Common Stock (determined on a fully diluted basis); and (f) to cause to be elected to the Board four non-employee directors nominated by the Board of Directors of the Company. 2 1.2 Certain Transactions 1.2.1 Company Capital Stock Owned by MWR In the event IES becomes the Beneficial Owner of 50% or more of the shares of capital stock of the Company beneficially owned by MWR, (a) the provisions of Section 1.1(c) shall be null and void and of no further force and effect, (b) at all meetings or votes, consents or authorizations of the Company's stockholders through the Expiration Date, IES shall vote, or use its best efforts to direct the voting of, all Excess Shares beneficially owned by IES with respect to the election of directors and all other matters either (i) in accordance with the recommendations of the Board of Directors of the Company or (ii) for or against or abstaining in the same proportion as the shares owned by all other stockholders (excluding IES and its Affiliates and Associates) are voted or abstained from voting with respect to such matter, (c) IES shall cause, or use its best efforts to cause, all shares of capital stock of the Company beneficially owned by IES to be represented in person or by proxy at all meetings of the Company's stockholders through the Expiration Date, and (d) IES shall not, and shall use its best efforts to cause its Affiliates and Associates not to, deposit any such shares of capital stock of the Company in a voting trust or enter into a voting agreement or other agreement of similar effect with any other person prior to the Expiration Date. 1.2.2 Company Capital Stock Owned by IES In the event MWR becomes the Beneficial Owner of 50% or more of the shares of capital stock of the Company beneficially owned by IES, (a) the provisions of Section 1.1(b) shall be null and void and of no further force and effect, (b) at all meetings or votes, consents or authorizations of the Company's stockholders through the Expiration Date, MWR shall vote, or use its best efforts to direct the voting of, all Excess Shares beneficially owned by MWR with respect to the election of directors and all other matters either (i) in accordance with the recommendations of the Board of Directors of the Company or (ii) for or against or abstaining in the same proportion as the shares owned by all other stockholders (excluding MWR and its Affiliates and Associates) are voted or abstained from voting with respect to such matter, (c) MWR shall cause, or use its best efforts to cause, all shares of capital stock of the Company beneficially owned by MWR to be represented in person or by proxy at all meetings of the Company's stockholders through the Expiration Date, and (d) MWR shall not, and shall use its best efforts to cause its Affiliates and Associates not to, deposit any such shares of capital stock of the Company in a voting trust or enter into a voting agreement or other agreement of similar effect with any other person prior to the Expiration Date. 1.2.3 Company Capital Stock Owned by MWR and IES In the event a third party becomes the Beneficial Owner of 50% or more of the shares of capital stock of the Company beneficially owned by IES and 3 50% or more of the shares of capital stock of the Company beneficially owned by MWR, (a) the provisions of Sections 1.1(b) and 1.1(c) shall be null and void and of no further force and effect, (b) at all meetings or votes, consents or authorizations of the Company's stockholders through the Expiration Date, IES and MWR shall vote, or use their respective best efforts to direct the voting of, all Excess Shares of capital stock of the Company beneficially owned by such third party with respect to the election of directors and all other matters either (i) in accordance with the recommendations of the Board of Directors of the Company or (ii) for or against or abstaining in the same proportion as the shares owned by all other stockholders (excluding IES, MWR and their respective Affiliates and Associates) are voted or abstained from voting with respect to such matter, (c) IES and MWR shall cause, or use their best efforts to cause, all shares of capital stock of the Company beneficially owned by them to be represented in person or by proxy at all meetings of the Company's stockholders through the Expiration Date, and (d) IES and MWR shall not, and shall use their best efforts to cause their respective Affiliates and Associates not to, deposit any such shares of capital stock of the Company in a voting trust or enter into a voting agreement or other agreement of similar effect with any other person prior to the Expiration Date. 1.2.4 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: (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, 4 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. (c) "Excess Shares" shall mean, with respect to the shares of capital stock of the Company beneficially owned by a person, any shares of capital stock of the Company beneficially owned by such person that, when aggregated with all shares of capital stock of the Company beneficially owned by such person and any of such person's Affiliates or Associates, represent more than 25% of the voting power of the outstanding capital stock of the Company. (d) "Expiration Date" shall mean October 23, 1999. 2. STANDSTILL Each of IES, MWR and MCG (each a "Strategic Investor" and collectively, the "Strategic Investors") hereby severally agrees that prior to June 10, 1999, none of such Strategic Investors nor any Affiliate thereof, will (and each such Strategic Investor will not assist or encourage others to), directly or indirectly, acquire or agree, offer, seek or propose to acquire, or cause to be acquired, ownership (including, but not limited to, beneficial ownership) of any securities issued by the Company or any of its subsidiaries, or any rights or options to acquire such ownership (including from a third party), except (a) to the extent expressly set forth in this Agreement, (b) as consented prior thereto in writing by the Company's Board of Directors, (c) upon conversion of any Class B common stock, $.01 par value per share, of the Company into Class A Common Stock pursuant to the terms thereof, (d) with respect to transfers of equity securities between or among a Strategic Investor and such party's wholly owned subsidiaries, parent corporation, or other wholly owned subsidiaries of such parent corporation, (e) in connection with a business combination between or among Strategic Investors, or (f) in the case of IES (or any Affiliate thereof), with respect to the grant, vesting or exercise of stock options. 5 3. TRANSFERS OF SECURITIES 3.1 Restrictions on Transfers (a) Each Principal Stockholder hereby severally agrees that until the earlier of (i) the first anniversary of the Effective Date and (ii) March 31, 1999, such Principal Stockholder 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 Principal Stockholder (or, in the case of a Principal Stockholder that is a trust, the trustee thereof) without the prior written consent of the Company provided, however that any CCI Shareholder may transfer -------- ------- Securities to any other CCI Shareholder (or a trust for the primary benefit of any CCI Shareholder), or, in the case of a CCI Shareholder that is a trust, to any beneficiary of such trust (or a trust for the primary benefit of such beneficiary), 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 Principal Stockholder, and any such transfer shall not constitute a "Transfer" for purposes of this Agreement. (b) In the event that the Company consents to any Transfer of Securities by a Principal Stockholder (a "Transferring Stockholder"), each other Principal Stockholder shall, notwithstanding the provisions of Section 3.1(a), have the right to Transfer a percentage of the total amount of Securities beneficially owned by such Principal Stockholder (or, in the case of a Principal Stockholder that is a trust, the trustee thereof) equal to the percentage of the total number of Securities beneficially owned by the Transferring Stockholder that the Company has consented may be Transferred by such Transferring Stockholder. (c) For purposes of this Section 3.1, MWR and MCG shall be deemed to be a single Principal Stockholder, 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 Company pursuant to Section 3.1 grants a Transferring Stockholder the opportunity to register Securities for Transfer under the Securities Act of 1933, as amended (the "Securities Act"), the Company shall grant each other Principal Stockholder, notwithstanding Section 3.1(a), 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 amount of Securities beneficially owned by such Principal Stockholder (or, in the case of a Principal Stockholder that is a trust, the trustee thereof) equal to the percentage of the total number of Securities beneficially owned by the Transferring Stockholder that such Transferring Stockholder is registering for Transfer under 6 the Securities Act, on the same terms and conditions as the Transferring Stockholder (such Transferring Stockholder and any Principal Stockholder registering any Securities for Transfer under the Securities Act pursuant hereto being a "Registering Transferor"). (b) If the Board establishes a committee (a "Pricing Committee") to authorize and approve the price and any other terms of any Transfer of Securities registered under the Securities Act pursuant to this Section 3.2 in which Lumpkin or any CCI Shareholder is participating as a Registering Transferor, the Company will use its best efforts to cause Lumpkin to be nominated to such Pricing Committee. (c) For purposes of this Section 3.2, MWR and MCG shall be deemed to be a single Principal Stockholder, and Lumpkin and all of the CCI Shareholders shall be deemed to be a single Principal Stockholder. 4. REPRESENTATIONS AND WARRANTIES 4.1 Representations and Warranties of Non-individual Stockholders. Each non-individual Principal Stockholder hereby represents and warrants, as of the date of this Agreement, to the Company and to each other Principal Stockholder as follows: 4.1.1 Authorization Such Principal Stockholder 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 Principal Stockholder, 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 Stockholder pursuant hereto, when executed and delivered in accordance with the provisions hereof, shall be a valid and binding obligation of such Principal Stockholder, enforceable in accordance with its terms (with the aforesaid exceptions). 7 4.2 Representations and Warranties of Individual Stockholders Each Principal Stockholder who is an individual hereby represents and warrants, as of the date of this Agreement, to the Company and to each other Principal Stockholder as follows: 4.2.1. Power and Authority Such Principal Stockholder has the legal capacity and all other necessary 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 Principal Stockholder, 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 Principal Stockholder pursuant hereto, when executed and delivered in accordance with the provisions hereof, shall be a valid and binding obligation of such Principal Stockholder, 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 Principal Stockholder 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). 8 5. MISCELLANEOUS 5.1 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 time of this Agreement. 5.2 Entire Agreement; Amendment This Agreement constitutes the entire agreement among the parties hereto as of the date hereof with respect to the matters contemplated herein, and it supersedes all prior oral or written agreements, commitments or understandings with respect to the matters provided for herein (including the agreements, commitments or understandings with respect to the matters provided for herein in the Investor Agreement). No amendment, modification or discharge of this Agreement shall be valid or binding unless set forth in writing and duly executed by the party against whom enforcement of the amendment, modification, or discharge is sought. 5.3 Limitation on Benefit 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. 5.4 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. 9 5.5 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.6 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: Casey D. Mahon Facsimile: (319) 298-7901 (ii) If to IES: IES Investments Inc. 200 1st Street SE Cedar Rapids, IA 52401 Attention: Peter W. Dietrich Facsimile: (319) 398-4483 (iii) If to MWR: MWR Investments Inc. 666 Grand Avenue P. O. Box 657 Des Moines, IA 50306-9244 Attention: Alan Wells, President Facsimile: (515) 242-4038 (iv) If to Lumpkin: 5 Lafayette Avenue Mattoon, Il 61938 Facsimile: 10 (v) If to any CCI Shareholder: c/o Mr. Richard A. Lumpkin 5 Lafayette Avenue Mattoon, Il 61938 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.7 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. 11 IN WITNESS WHEREOF, the undersigned have duly executed this Agreement, or have caused this Agreement to be duly executed on their behalf, as of the day and year first hereinabove set forth. MCLEODUSA INCORPORATED MWR INVESTMENTS INC. By: /s/ Clark E. McLeod By: /s/ Alan Wells --------------------- ---------------- Name: Name: Alan Wells Title: Title: President MIDWEST CAPITAL IES INVESTMENTS INC. GROUP, INC. By: /s/ Stephen W. Southwick By: /s/ Alan Wells -------------------------- ---------------- Name: Stephen W. Southwick Name: Alan Wells Title: Secretary Title: President /s/ Clark E. McLeod /s/ Mary E. McLeod ------------------- ------------------ Clark E. McLeod Mary E. McLeod /s/ Richard A. Lumpkin Richard A. Lumpkin ---------------------- By and on Behalf of Each Richard A. Lumpkin of the Shareholders Named on Schedule I hereto ---------- /s/ Richard A. Lumpkin ---------------------- Name: Title: 12