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-