<PAGE>

                                                                    Exhibit 4.28

                          THIRD AMENDED AND RESTATED

                     JANUARY 1999 STOCKHOLDERS' AGREEMENT


          This Third Amended and Restated January 1999 Stockholders' Agreement
(this "Agreement") is entered into as of March 10, 2000, by and among McLeodUSA
Incorporated, a Delaware corporation (the "Company"); Alliant Energy
Corporation, a Wisconsin corporation ("AEC"); Alliant Energy Investments, Inc.,
an Iowa corporation and indirect wholly owned subsidiary of AEC ("AEI");
Heartland Properties, Inc., a Wisconsin corporation and indirect wholly owned
subsidiary of AEC ("Heartland"); LNT Communications LLC, an Iowa limited
liability company and indirect wholly owned subsidiary of AEC ("LNT"); Alliant
Energy Foundation, Inc., a Wisconsin corporation (non-profit) ("AEF" and
together with AEC, AEI, Heartland and LNT, the "AEC Entities"); Clark E. McLeod
("McLeod"); Mary E. McLeod (together with McLeod, the "McLeods"); M/C Investors
L.L.C., a Delaware limited liability company ("M/C Investors");
Media/Communications Partners III Limited Partnership, a Delaware limited
partnership ("M/C Partners" and together with M/C Investors, the "M/C
Stockholders"); Richard A. Lumpkin ("Lumpkin") and certain of the former
shareholders of Consolidated Communications Inc. ("CCI") and certain permitted
transferees of certain of the former CCI shareholders in each case who are
listed in Schedule I hereto (the "Principal CCI Shareholders"); and for purposes
          ----------
of Sections 4, 5.6, 5.8(d), 5.11 and the first sentence of Section 5.3 only,
certain of the other former CCI shareholders and certain permitted transferees
of certain of the other former CCI shareholders in each case who are listed in
Schedule II hereto (the "Other CCI Shareholders").  The AEC Entities, the
-----------
McLeods, Lumpkin and the Principal CCI Shareholders are referred to herein
collectively as the "Original Stockholders" and individually as an "Original
Stockholder."

          WHEREAS, the Company, AEC, AEI, Heartland, AEF, the McLeods, the M/C
Stockholders, Lumpkin, the Principal CCI Shareholders and the Other CCI
Shareholders are parties to a Second Amended and Restated January 1999
Stockholders' Agreement, entered into as of December 17, 1999 (the "Second
Amended and Restated January 1999 Stockholders' Agreement");

          WHEREAS, the Company, AEC, AEI, Heartland, AEF, the McLeods, the M/C
Stockholders, Lumpkin and the Principal CCI Shareholders desire to add LNT as a
party to this Agreement as a result of the transfer of certain shares of the
Company's Class A common stock, par value $.01 per share (the "Class A Common
Stock"), by an Affiliate (as defined in Section 2.2) of AEC to LNT;
<PAGE>

          WHEREAS, the Other CCI Shareholders no longer desire to be parties to
this Agreement and the Company, the M/C Stockholders and the Original
Stockholders desire to terminate the Other CCI Shareholders as parties to this
Agreement;

          WHEREAS, the Company, the Original Stockholders and the M/C
Stockholders deem it to be in the best interests of the Company and its
stockholders to provide for the continuity and stability of the business and
policies of the Company on the terms and conditions hereinafter set forth;

          WHEREAS, concurrently with execution and delivery of this Agreement,
the Company, the Original Stockholders and the Other CCI Shareholders are
entering into an amendment and restatement of the Second Amended and Restated
November 1998 Stockholders' Agreement, entered into as of December 17, 1999; and

          WHEREAS, the Company, the Original Stockholders and the M/C
Stockholders desire to amend and restate the Second Amended and Restated January
1999 Stockholders' Agreement in its entirety with 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

     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 Original
Stockholder and the M/C Stockholders, for so long as each such Original
Stockholder and the M/C Stockholders beneficially and continuously owns 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 of the Company (the "Board of Directors" or the
               "Board") at up to thirteen (13) directors;

                                      -2-
<PAGE>

          (b)  to cause to be elected to the Board one (1) director designated
               by the AEC Entities, for so long as the AEC Entities 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);

          (c)  to cause Lumpkin to be elected to the Board, for so long as
               Lumpkin and the Principal CCI Shareholders 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);

          (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 two million five hundred thousand (2,500,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 M/C Stockholders, for so long as the M/C 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 (b) through (e) above upon the
               earlier to occur of such designated 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 (b)
               through (e) above 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 that the party or parties identified in paragraphs (b)
               through (e) above no longer collectively beneficially and
               continuously own at least two million five hundred thousand
               (2,500,000)

                                      -3-
<PAGE>

               shares of Class A Common Stock (subject to adjustment pursuant to
               Section 5.1) 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 seven (7) non-employee directors.

          For purposes of this Section 2.1, (i) the McLeods shall be deemed to
be a single Original Stockholder of the Company, (ii) the M/C Stockholders shall
be deemed to be a single stockholder of the Company, and the M/C Stockholders
shall be deemed to own shares "continuously" as long as the shares of the M/C
Stockholders are owned by the M/C Stockholders or an M/C Stockholder Permitted
Transferee (as defined in Section 3.1), (iii) Lumpkin and all of the Principal
CCI Shareholders shall be deemed to be a single Original Stockholder of the
Company, and the Principal CCI Shareholders shall be deemed to own shares
"continuously" as long as the shares of the Principal CCI Shareholders are owned
by the Principal CCI Shareholders or a CCI Permitted Transferee (as defined in
the Third Amended and Restated November 1998 Stockholders' Agreement (as defined
in Section 2.2)), and (iv) the AEC Entities shall be deemed to be a single
Original Stockholder of the Company, and the AEC Entities shall be deemed to own
shares "continuously" as long as the shares of the AEC Entities are owned by the
AEC Entities or an AEC Permitted Transferee (as defined in the Third Amended and
Restated November 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:

                    (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

                                      -4-
<PAGE>

                          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 or the Third
               Amended and Restated November 1998 Stockholders' Agreement.

               (c)  "Effective Date" shall mean March 10, 2000.

               (d)  "Expiration Date" shall mean December 31, 2001.

               (e)  "Merger" shall mean the merger of Ovation Communications,
               Inc. with and into Bravo Acquisition Corporation pursuant to the
               terms and conditions of the Merger Agreement.

               (f)  "Merger Agreement" shall mean the Agreement and Plan of
               Merger, dated as of January 7, 1999, by and among the Company,
               Bravo Acquisition Corporation, Ovation Communications, Inc. and
               certain of the stockholders of Ovation Communications, Inc.

               (g)  "Stock Split" shall mean that certain two-for-one stock
               split in the form of a stock dividend paid on July 26, 1999 to
               stockholders of record on July 12, 1999 effected by the Company
               with respect to its Class A Common Stock.

                                      -5-
<PAGE>

               (h)  "Third Amended and Restated November 1998 Stockholders'
               Agreement" shall mean the Third Amended and Restated November
               1998 Stockholders' Agreement, entered into as of March 10, 2000
               by and among the Company, the Original Stockholders and the Other
               CCI Shareholders.

3.   TRANSFERS OF SECURITIES

     3.1  Restrictions on Transfers

          (a)  Except as otherwise provided in this Section 3.1 or Section 3.2,
the M/C Stockholders hereby agree that until the Expiration Date, the M/C
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
M/C 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 the M/C Stockholders may transfer Securities to any
--------  -------
beneficial owner or Affiliate of the M/C Stockholders, 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 this Agreement may be
amended or amended and restated from time to time) as an M/C Stockholder with
respect to the shares being transferred pursuant to this Section (any such M/C
Stockholder transferee pursuant to the foregoing proviso, an "M/C 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 M/C Stockholder Permitted Transferees and then at any time directly
or indirectly disposing of all or any portion of such party's interest in any
such M/C 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 Third Amended and Restated November 1998
Stockholders' Agreement) pursuant to Section 3.1(a) of the Third Amended and
Restated November 1998 Stockholders' Agreement upon the written request of such
Principal Stockholder (the "Transferring Principal Stockholder") and except as
otherwise provided in Section 3.1(b) and Section 3.2 of this Agreement, the M/C
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 M/C Stockholders equal to the percentage of the total
number of Securities beneficially owned by the Transferring Principal
Stockholder that the Board of

                                      -6-
<PAGE>

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 M/C Stockholders pursuant to this Section 3.1(a) upon the
written request of the M/C Stockholders (the "Transferring M/C Stockholders"),
and except as otherwise provided in Section 3.1(b) and Section 3.2 of the Third
Amended and Restated November 1998 Stockholders' Agreement, each Principal
Stockholder shall, notwithstanding the provisions of Section 3.1(a) of the Third
Amended and Restated November 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 M/C Stockholders that the
Board of Directors has consented may be Transferred by such Transferring M/C
Stockholders.

          (b)  In addition to the provisions of Section 3.1(a), for the period
commencing for the quarter ending March 31, 2000 and ending on the Expiration
Date, the Board shall determine prior to the public release of the 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 one hundred thousand (100,000)
shares of Class A Common Stock per quarter, subject to adjustment pursuant to
Section 5.1) that may be Transferred by the M/C 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 M/C 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 M/C 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 Third Amended and Restated November 1998
Stockholders' Agreement, the Company shall grant the M/C 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 Third Amended and Restated
November 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 M/C Stockholders for any particular quarter pursuant
to this Section 3.1(b), the Board shall determine an equal Transfer Amount for
such quarter with respect to each Principal Stockholder pursuant to

                                      -7-
<PAGE>

Section 3.1(b) of the Third Amended and Restated November 1998 Stockholders'
Agreement.

          (c)  For the period commencing for the quarter ending March 31, 2000
and ending on the Expiration Date, the Company shall give the M/C 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 M/C
Stockholders shall provide written notice to the Company of the number of shares
of Class A Common Stock that the M/C Stockholders desire to Transfer pursuant to
Section 3.1(b).

          (d)  For purposes of this Section 3.1, the M/C Stockholders shall be
deemed to be a single stockholder of the Company, the McLeods shall be deemed to
be a single Principal Stockholder of the Company, Lumpkin and all of the
Principal CCI Shareholders shall be deemed to be a single Principal Stockholder
of the Company and the AEC Entities shall be deemed to be a single Principal
Stockholder of the Company.

     3.2  Registration Rights

          (a)  In the event that the Board of Directors consents pursuant to
Section 3.1(a) of the Third Amended and Restated November 1998 Stockholders'
Agreement to a Principal Stockholder's request for a Transfer 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 M/C 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 M/C 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 M/C 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
Third Amended and Restated November 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 M/C Stockholders that such Transferring M/C Stockholders are
registering under the Securities Act, on the same terms and conditions as the
Transferring M/C Stockholders.

                                      -8-
<PAGE>

          (b)  To the extent that the Company grants pursuant to Section 3.1(b)
of the Third Amended and Restated November 1998 Stockholders' Agreement a
Principal Stockholder the opportunity to register shares of Class A Common Stock
for Transfer under the Securities Act, the Company shall grant the M/C
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 Third
Amended and Restated November 1998 Stockholders' Agreement relating to the
reallocation of amounts among the Principal Stockholders.  To the extent that
the Company grants pursuant to Section 3.1(b) of this Agreement the M/C
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 Third Amended and Restated
November 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)  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 M/C Stockholders), the
Company, as determined by the Board of Directors, shall give written notice to
the M/C 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 M/C
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 M/C
Stockholders as of the Effective Time (as defined in the Merger Agreement) in
connection with the consummation of the Merger, subject to appropriate and
proportionate adjustment as a result of the Stock Split and subject to
adjustment pursuant to Section 5.1) to be registered by the Company under the
Securities Act (the "Registrable Amount") for Transfer by the M/C Stockholders
in connection with such offering during such period.  If the Board determines to
register shares of Class A Common Stock held by the M/C Stockholders pursuant to
this Section 3.2(c), the Company will promptly give written notice of such
determination to the M/C Stockholders, and thereupon the Company will use
commercially reasonable efforts to effect the registration of that portion of
the Registrable Amount that the M/C 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 M/C Stockholders shall be customary taking into account, among other things,
the nature of the offering and the M/C Stockholders' relationship with

                                      -9-
<PAGE>

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 M/C Stockholders, which
underwriting discounts and commissions shall be the responsibility of the M/C
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 Third
Amended and Restated November 1998 Stockholders' Agreement the Principal
Stockholders the opportunity to register shares of Class A Common Stock for
Transfer under the Securities Act, the Company shall grant the M/C 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 M/C 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 Third Amended
and Restated November 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 M/C
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 M/C
Stockholders.  If the Board determines to register shares of Class A Common
Stock held by the M/C Stockholders pursuant to this Section 3.2(d), the Company
will promptly give written notice of such determination to the M/C Stockholders,
and thereupon the Company will use commercially reasonable efforts to effect the
registration of that portion of the Registrable Amount that the M/C 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 M/C Stockholders shall be customary taking
into account, among other things, the nature of the offering and the M/C
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 M/C Stockholders, which underwriting discounts and commissions shall be the
responsibility of the M/C 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 Third Amended and Restated November 1998
Stockholders' Agreement the Principal Stockholders the opportunity to register
shares of Class A Common Stock for Transfer under the Securities Act, the
Company shall grant the M/C 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 M/C Stockholders
the opportunity to register shares of Class A Common Stock for

                                      -10-
<PAGE>

Transfer under the Securities Act, the Company shall grant each Principal
Stockholder pursuant to Section 3.2(d) of the Third Amended and Restated
November 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 M/C Stockholders shall be
deemed to be a single stockholder of the Company, the McLeods shall be deemed to
be a single Principal Stockholder of the Company, Lumpkin and all of the
Principal CCI Shareholders shall be deemed to be a single Principal Stockholder
of the Company and the AEC Entities shall be deemed to be a single Principal
Stockholder of the Company.

          (f)  Notwithstanding any other provision of this Agreement, to the
extent the Company has undertaken to register Securities of the M/C Stockholders
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 M/C
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

                                      -11-
<PAGE>

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:

          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

                                      -12-
<PAGE>

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 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

          Other than the Third Amended and Restated November 1998 Stockholders'
Agreement with respect to the parties thereto and as set forth therein, this
Agreement constitutes the entire agreement among the parties hereto as of the
date hereof with respect to the specific matters contemplated herein, and it
supersedes all prior oral or written agreements, commitments or understandings
with respect to the matters provided for herein.  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 M/C Stockholders shall be valid and binding with respect to all M/C
Stockholders if such amendment, modification or discharge is executed by those
M/C Stockholders holding a majority of the shares of Class A Common Stock issued
to the M/C 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).

                                      -13-
<PAGE>

     5.4  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.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) 790-7901

                                      -14-
<PAGE>

          (ii)  If to the AEC Entities:

                Alliant Energy Investments, Inc.
                200 1st Street SE
                Cedar Rapids, IA 52401
                Attention:  James E. Hoffman
                Facsimile:  (319) 398-4204

          (iii) If to Lumpkin or any Principal 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, IL  60606
                Attention:  David R. Hodgman, Esq.
                Facsimile:  (312) 258-5600

          (iv)  If to the M/C Stockholders:
                c/o Media/Communications Partners III
                Limited Partnership
                75 State Street
                Boston, MA  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

                                      -15-
<PAGE>

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 an Original Stockholder (and not as to the Company and the M/C
Stockholders) at such time as the Third Amended and Restated November 1998
Stockholders' Agreement shall terminate and be of no further force or effect
with respect to such Original Stockholder.

          (b)  If (i) during any Annual Period the Board of Directors has not
provided the M/C 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 M/C Stockholders as of the Effective Time in
connection with the consummation of the Merger, subject to appropriate and
proportionate adjustment as a result of the Stock Split and subject to
adjustment pursuant to Section 5.1 or (ii) the Third Amended and Restated
November 1998 Stockholders' Agreement has been terminated by all parties
thereto, then the M/C Stockholders may terminate this Agreement by providing
written notice of termination to the Company and the Original Stockholders (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 clause (b)(ii) above, at any
time following such termination, 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 M/C Stockholders
pursuant to Section 5.8(b), this Agreement shall terminate on the Expiration
Date.

          (d)  This Agreement is hereby terminated with respect to each of the
Other CCI Shareholders, such that all rights and obligations hereunder shall
cease, and this Agreement shall be of no further force or effect, with respect
to each of the Other CCI Shareholders.

          (e)  For purposes of this Section 5.8, the M/C Stockholders shall be
deemed to be a single stockholder of the Company, the McLeods shall be deemed to
be a single Original Stockholder of the Company, Lumpkin and all of the
Principal CCI Shareholders shall be deemed to be a single Original Stockholder
of the Company, and the AEC Entities shall be deemed to be a single Original
Stockholder of the Company.

                                      -16-
<PAGE>

     5.9   Publicity

           The M/C 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 M/C Stockholders within which this
Agreement or the contents hereof are referenced or described.

     5.10  Appointment of Representative

           (a)  Each of the M/C Stockholders hereby appoints M/C Partners, 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 M/C 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 M/C Stockholders, as fully
as if each of the M/C 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 M/C
Stockholders.

           (b)  Each of the Principal 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 Principal 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
Principal CCI Shareholders, as fully as if each of the Principal 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
Principal CCI Shareholders.

                                      -17-
<PAGE>

     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.


                 [Remainder of Page Intentionally Left Blank]

                                      -18-
<PAGE>

          IN WITNESS WHEREOF, the undersigned have duly executed and delivered
this Third Amended and Restated January 1999 Stockholders' Agreement, or have
caused this Third Amended and Restated January 1999 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/CFO



     /s/ Clark E. McLeod                               /s/ Mary E. McLeod
---------------------------------             ----------------------------------
Clark E. McLeod                               Mary E. McLeod


M/C INVESTORS L.L.C.



By: /s/ Peter H.O. Claudy
    ---------------------------
   Name:  Peter H.O. Claudy
   Title:  Manager


MEDIA/COMMUNICATIONS PARTNERS III LIMITED PARTNERSHIP

By:  M/C III L.L.C., its General Partner



By: /s/ Peter H.O. Claudy
    ----------------------------
   Name:  Peter H.O. Claudy
   Title:  Manager

                                      -19-
<PAGE>

ALLIANT ENERGY CORPORATION, INC.


By: /s/ James E. Hoffman
    -----------------------------
   Name:  James E. Hoffman
   Title:  Executive Vice President
            Business Development


ALLIANT ENERGY FOUNDATION


By: /s/ Edward M. Gleason
    ---------------------------
   Name:  Edward M. Gleason
   Title:  Treasurer


ALLIANT ENERGY INVESTMENTS, INC.


By: /s/ James E. Hoffman
    -----------------------------
   Name:  James E. Hoffman
   Title:  President, Alliant Energy Resources


HEARTLAND PROPERTIES, INC.


By: /s/ Henry Wertheimer
    ---------------------------
   Name:  Henry Wertheimer
   Title:  Vice President/Treasurer


LNT COMMUNICATIONS LLC
By: Alliant Energy Resources, Inc., its sole member


By: /s/ James E. Hoffman
    ---------------------------
   Name:  James E. Hoffman
   Title:  President


      /s/ Richard A. Lumpkin                        /s/ Gail G. Lumpkin
-------------------------------------          ---------------------------------
Richard A. Lumpkin                             Gail G. Lumpkin

                                      -20-
<PAGE>

The two trusts created under the Mary   The two trusts created under the Richard
Green Lumpkin Gallo Trust Agreement     Adamson Lumpkin Grandchildren's Trust
dated December 29, 1989, one for the    dated September 5, 1980, one for the
benefit of each of:                     benefit of each of:
     Benjamin Iverson Lumpkin                Benjamin Iverson Lumpkin
     Elizabeth Arabella Lumpkin              Elizabeth Arabella Lumpkin



United States Trust Company             United States Trust Company
of New York, Trustee                    of New York, Trustee



By:  /s/ Loraine B. Tsavaris            By:  /s/ Loraine B. Tsavaris
     ---------------------------             ---------------------------
    Name:  Loraine B. Tsavaris              Name:  Loraine B. Tsavaris
    Title:  Managing Director               Title:  Managing Director

The trust established by  Richard       The two 1990 Personal Income Trusts
Adamson Lumpkinunder the Trust          established by Richard A. Lumpkin, dated
Agreement dated February 6, 1970,       April 20, 1990, one for the benefit of
for the benefit of Richard Anthony      each of:
Lumpkin.                                     Benjamin Iverson Lumpkin
                                             Elizabeth Arabella Lumpkin

United States Trust Company
of New York, Trustee                              /s/ David R. Hodgman
                                        ----------------------------------------
                                        David R. Hodgman, Trustee

By:  /s/ Loraine B. Tsavaris                      /s/ Steven L. Grissom
     ---------------------------        ----------------------------------------
    Name:  Loraine B. Tsavaris          Steven L. Grissom, Trustee
    Title:  Managing Director


                                      -21-
<PAGE>

FOR PURPOSES OF SECTIONS 4, 5.6, 5.8(d), 5.11 AND THE FIRST SENTENCE OF SECTION
5.3 ONLY:

Margaret Lumpkin Keon Trust             Mary Lee Sparks Trust
dated May 13, 1978                      dated May 13, 1978


/s/ Margaret Lumpkin Keon               /s/ Mary Lee Sparks
------------------------------------    ---------------------------------
Margaret Lumpkin Keon, as Trustee       Mary Lee Sparks, as Trustee


                                        /s/ Steven L. Grissom
                                        ---------------------------------
                                        Steven L. Grissom, as Trustee


/s/ Mary Lee Sparks
------------------------------------
Mary Lee Sparks


The ten trusts created under the        The ten trusts created under the
Mary Green Lumpkin Gallo Trust          Richard Adamson Lumpkin
Agreement dated December 29,            Grandchildren's Trust dated
1989, one for the benefit of each of:   September 5, 1980, one for the benefit
    Joseph John Keon III,               of each of:
    Katherine Stoddert Keon,                Joseph John Keon III,
    Lisa Anne Keon,                         Katherine Stoddert Keon,
    Margaret Lynley Keon,                   Lisa Anne Keon,
    Pamela Keon Vitale,                     Margaret Lynley Keon,
    Susan Tamara Keon DeWyngaert,           Pamela Keon Vitale,
    Anne Romayne Sparks,                    Susan Tamara Keon DeWyngaert,
    Barbara Lee Sparks,                     Anne Romayne Sparks,
    Christina Louise Sparks, and            Barbara Lee Sparks,
    John Woodruff Sparks                    Christina Louise Sparks, and
                                            John Woodruff Sparks

United States Trust Company             United States Trust Company of
of New York, Trustee                    New York, Trustee


                                        By: /s/ Loraine B. Tsavaris
By: /s/ Loraine B. Tsavaris                 -----------------------------
    --------------------------------        Name:  Loraine B. Tsavaris
    Name:  Loraine B. Tsavaris              Title: Managing Director
    Title: Managing Director

                                      -22-
<PAGE>

The two trusts established by Richard   The ten 1990 Personal Income Trusts
Adamson Lumpkin under the Trust         established by Margaret L. Keon and
Agreement dated February 6, 1970,       Mary Lee Sparks, each dated April 20,
one for the benefit of each of:         1990, one for the benefit of each of:
    Margaret Anne Keon, and
    Mary Lee Sparks                        Joseph John Keon III,
                                           Katherine Stoddert Keon,
                                           Lisa Anne Keon,
                                           Margaret Lynley Keon,
United States Trust Company                Pamela Keon Vitale,
of New York, Trustee                       Susan Tamara Keon DeWyngaert,
                                           Anne Romayne Sparks,
                                           Barbara Lee Sparks,
                                           Christina Louise Sparks, and
By: /s/ Loraine B. Tsavaris                John Woodruff Sparks
    ------------------------------
    Name:  Loraine B. Tsavaris          /s/ David R. Hodgman
    Title: Managing Director            --------------------------------------
                                        David R. Hodgman, Trustee

                                        /s/ Steven L. Grissom
                                        --------------------------------------
                                        Steven L. Grissom, Trustee

                                      -23-
<PAGE>

                                  SCHEDULE I


Richard A. Lumpkin

Gail G. Lumpkin

United States Trust Company of New York, as Trustee of two trusts created under
the Mary Green Lumpkin Gallo Trust Agreement dated December 29, 1989, one for
the benefit of each of Benjamin Iverson Lumpkin and Elizabeth Arabella Lumpkin.

United States Trust Company of New York, as Trustee of two trusts created under
the Richard Adamson Lumpkin Grandchildren's Trust dated September 5, 1980, one
for the benefit of each of Benjamin Iverson Lumpkin and Elizabeth Arabella
Lumpkin.

United States Trust Company of New York, as Trustee of the trust established by
Richard Adamson Lumpkin under the Trust Agreement dated February 6, 1970, for
the benefit of Richard Anthony Lumpkin.

David R. Hodgman and Steven L. Grissom, as Trustees of two 1990 Personal Income
Trusts established by Richard A. Lumpkin, each dated April 20, 1990, one for the
benefit of each of Benjamin Iverson Lumpkin and Elizabeth Arabella Lumpkin.
<PAGE>

                                  SCHEDULE II


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.

Mary Lee Sparks

United States Trust Company of New York, as Trustee of ten 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,
Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks, and John
Woodruff Sparks.

United States Trust Company of New York, as Trustee of ten 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, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise Sparks,
and John Woodruff Sparks.

United States Trust Company of New York, as Trustee of two trusts established by
Richard Adamson Lumpkin under the Trust Agreement dated February 6, 1970, one
for the benefit of each of Margaret Anne Keon and Mary Lee Sparks.

David R. Hodgman and Steven L. Grissom, as Trustees of ten 1990 Personal Income
Trusts established by Margaret L. Keon and Mary Lee Sparks, 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, Anne Romayne Sparks, Barbara Lee Sparks, Christina Louise
Sparks, and John Woodruff Sparks.