<PAGE>

===============================================================================

     As filed with the Securities and Exchange Commission on June 22, 2000

                                                  Registration No. 333-_________



                      SECURITIES AND EXCHANGE COMMISSION
                            Washington, D.C.  20549
                              __________________
                                   FORM S-8

                            REGISTRATION STATEMENT
                                     UNDER
                          THE SECURITIES ACT OF 1933

                            McLEODUSA INCORPORATED
            ------------------------------------------------------
            (Exact name of registrant as specified in its charter)

            Deleware                                   42-1407240
---------------------------------        ------------------------------------
   (State or other jurisdiction          (I.R.S. employer identification no.)
of incorporation or organization)


                           McLeodUSA Technology Park
                       6400 C Street, SW, P.O. Box 3177
                         Cedar Rapids, Iowa 52406-3177
                         -----------------------------
                   (Address of principal executive offices)

                            McLeodUSA Incorporated
                        1996 Employee Stock Option Plan
        --------------------------------------------------------------
                           (Full title of the plan)

                                 Randall Rings
                 Vice President, General Counsel and Secretary
                            McLeodUSA Incorporated
                           McLeodUSA Technology Park
                       6400 C Street, SW, P.O. Box 3177
                         Cedar Rapids, Iowa 52406-3177
                                (319) 364-0000
-------------------------------------------------------------------------------
(Name, address and telephone number, including area code, of agent for service)


                        CALCULATION OF REGISTRATION FEE

<TABLE>
<CAPTION>
                                                               Proposed                       Proposed
      Title of securities        Amount to be              maximum offering              maximum aggregate         Amount of
       to be registered           registered               price per share (1)           offering price (1)    registration fee (1)
-----------------------------------------------------------------------------------------------------------------------------------
<S>                              <C>                      <C>                           <C>                            <C>
Class A Common Stock, par
 value $.01                      100,000,000                  $23.6875                     $2,368,750,000             $625,350

===================================================================================================================================
</TABLE>

(1)  Estimated pursuant to Rule 457(c) and (h) solely for purposes of
calculating the amount of the registration fee, based on the average of the high
and low prices per share of McLeodUSA Incorporated Class A Common Stock, par
value $.01 per share, on June 15, 2000, as reported on the Nasdaq National
Market.

This Registration Statement incorporates by reference the information contained
in earlier registration statements on Form S-8 filed by McLeodUSA Incorporated
(the "Company") with the Securities and Exchange Commission on January 9, 1998
(Registration No. 333-44025) and on July 9, 1996 (Registration No. 333-07809) to
the extent relating to the McLeodUSA Incorporated 1996 Employee Stock Option
Plan, as amended (the "Plan").

===============================================================================
<PAGE>

                               EXPLANATORY NOTE

     As permitted by General Instruction E to the Form S-8, this Registration
Statement incorporates by reference the information contained in earlier
registration statements on Form S-8 filed by McLeodUSA Incorporated (the
"Company") with the Securities and Exchange Commission on January 9, 1998
(Registration No. 333-44025) and on July 9, 1996 (Registration No. 333-07809) to
the extent relating to the McLeodUSA Incorporated 1996 Employee Stock Option
Plan, as amended (the "Plan").  Pursuant to these earlier registration
statements on Form S-8, the Company has previously registered 67,200,000 shares
of Class A Common Stock (adjusted to reflect two stock splits, described below).

     The Plan was duly adopted and approved by the Board of Directors on March
28, 1996 and was duly approved by the stockholders of the Company on April 30,
1996.  On March 27, 1997, the Board of Directors of the Company approved and
adopted an amendment to Article 4 of the Plan to increase the number of shares
of Class A Common Stock available for issuance thereunder to 225,000,000
(adjusted to reflect two stock splits, described below).  The Company's
stockholders approved such amendment to the Plan at the annual meeting of
stockholders held on May 29, 1997.

     The Company announced on June 30, 1999 a two-for-one stock split to be
effected in the form of a stock dividend.  The record date for the stock split
was July 12, 1999.  Stockholders of record at the market close on that date
received one additional share of Class A Common Stock for each share held.
Distribution of the additional shares took place on July 26, 1999.  In
connection with this stock dividend, the Company made a proportionate adjustment
to the number and exercise price of the options outstanding on July 26, 1999.

     On February 29, 2000, the Company announced a three-for-one stock split to
be effected in the form of a stock dividend.  The record date for the stock
split was April 4, 2000.  Stockholders of record at market close on that date
received two additional shares of Class A Common Stock for each share held.
Distribution of the additional shares took place on April 24, 2000.  In
connection with this stock dividend, the Company made a proportional adjustment
to the number and exercise price of the options outstanding on April 24, 2000.

     The Board of Directors approved and adopted various amendments to the Plan
on October 30, 1997, December 19, 1997, March 26, 1998 and September 24, 1998.
On April 12, 2000, the Board of Directors of the Company approved and adopted,
subject to stockholder approval, amendments to the Plan.  The Company's
stockholders approved such Plan as amended at a meeting of stockholders held on
May 31, 2000.

     Except for the foregoing amendments, the Plan remains unchanged.

                                      -2-
<PAGE>

                                    PART II

              INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

<TABLE>
<CAPTION>
Item 8.  Exhibits.

  Exhibit
  Number                               Description
  ------                               -----------
<S>      <C>
    4.1  McLeodUSA Incorporated 1996 Employee Stock Option Plan, as amended and
         restated, filed as Exhibit A to the Company's definitive proxy
         statement flied with the Commission on April 26, 2000 and incorporated
         herein by reference

    5.1  Opinion of Hogan & Hartson L.L.P.

   23.1  Consent of  Arthur Andersen LLP

   23.2  Consent of Hogan & Hartson L.L.P. (included in Exhibit 5.1).

   24.1  Power of Attorney (included on signature page).

</TABLE>

                                      -3-
<PAGE>

                                  SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, as amended, the
registrant certifies that it has reasonable grounds to believe that it meets all
of the requirements for filing on Form S-8 and has duly caused this registration
statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Cedar Rapids, State of Iowa, as of June 22, 2000.

                            McLEODUSA INCORPORATED


                            By: /s/ Randall Rings
                                -----------------
                                Randall Rings
                                Vice President, General Counsel and Secretary



                               POWER OF ATTORNEY

     KNOW ALL MEN BY THESE PRESENTS, that each person whose signature appears
below constitutes and appoints Randall Rings as true and lawful attorney-in-
fact, with full power of substitution, for him and in his name, place and stead,
in any and all capacities, to sign any and all amendments to this registration
statement (including post-effective amendments), and to file the same, with all
exhibits thereto and other documents in connection therewith, with the
Securities and Exchange Commission, granting unto said attorney-in-fact and
agents full power and authority to do and perform each and every act and thing
requisite and necessary to be done in and about the premises, as fully to all
intents and purposes as he might or could do in person, hereby ratifying and
confirming all that said attorney-in-fact, or his substitute or substitutes, may
lawfully do or cause to be done by virtue hereof.

     Pursuant to the requirements of the Securities Act of 1933, as amended,
this registration statement has been signed by the following persons, in the
capacities indicated below, as of June 22, 2000.



<TABLE>
<CAPTION>

       Signature                                   Title
       ---------                                   -----
<S>                                          <C>

/s/ Clark E. McLeod                          Chairman, Chief Executive Officer
-------------------------------------------    and Director (Principal Executive
Clark E. McLeod                                Officer)

/s/ Richard A. Lumpkin                       Vice Chairman and Director
-------------------------------------------
Richard A. Lumpkin

/s/ Stephen C. Gray                          President and Chief Operating Officer;
-------------------------------------------  President and Chief Executive Officer-Local
Stephen C. Gray                              Services; Director

/s/ Roy A. Wilkens                           Chief Technology Officer; Chief Executive
-------------------------------------------  Officer and President-Data Services; Director
Roy A. Wilkens
</TABLE>

                                      -4-
<PAGE>

<TABLE>

<S>                                          <C>
/s/ Blake O. Fisher, Jr.                     Group Vice President and Director
-------------------------------------------
Blake O. Fisher, Jr.

/s/ J. Lyle Patrick                          Group Vice President and Chief Financial
-------------------------------------------  Officer (Principal Financial Officer and
J. Lyle Patrick                              Principal Accounting Officer)

/s/ Anne K. Bingaman                                             Director
-------------------------------------------
Anne K. Bingaman
/s/ Erskine B. Bowles                                            Director
-------------------------------------------
Erskine B. Bowles

/s/ Peter H.O. Claudy                                            Director
-------------------------------------------
Peter H.O. Claudy

/s/ Thomas M. Collins                                            Director
-------------------------------------------
Thomas M. Collins

                                                                 Director
-------------------------------------------
Robert J. Currey

/s/ Theodore R. Forstmann                                        Director
-------------------------------------------
Theodore R. Forstmann

/s/ Daniel R. Hesse                                              Director
-------------------------------------------
Daniel R. Hesse

/s/ James E. Hoffman                                             Director
-------------------------------------------
James E. Hoffman

/s/ Paul D. Rhines                                               Director
-------------------------------------------
Paul D. Rhines
</TABLE>

                                      -5-
<PAGE>

                                  EXHIBIT INDEX

<TABLE>
<CAPTION>

Exhibit
Number                            Description
------                            -----------

<S>    <C>
  4.1  McLeodUSA Incorporated 1996 Employee Stock Option Plan, as amended and
       restated, filed as Exhibit A to the Company's definitive proxy statement
       flied with the Commission on April 26, 2000 and incorporated herein by
       reference

  5.1  Opinion of Hogan & Hartson L.L.P.

 23.1  Consent of  Arthur Andersen LLP

 23.2  Consent of Hogan & Hartson L.L.P. (included in Exhibit 5.1).

 24.1  Power of Attorney (included on signature page).
</TABLE>



                                      -6-
[{"type": "S-8", "sequence": "1", "filename": "0001.txt", "description": "FORM S-8", "secsgml_size_bytes": 12967}]
{"company-data": {"conformed-name": "MCLEODUSA INC", "cik": "0000919943", "assigned-sic": "4812", "irs-number": "421407240", "state-of-incorporation": "DE", "fiscal-year-end": "1231"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-39872", "film-number": "659146"}, "business-address": {"street1": "6400 C ST SW", "street2": "PO BOX 3177", "city": "CEDAR RAPIDS", "state": "IA", "zip": "52406-3177", "phone": "3193640000"}, "mail-address": {"street1": "6400 C ST SW", "street2": "PO BOX 3177", "city": "CEDAR RAPIDS", "state": "IA", "zip": "52406-3177"}, "former-company": {"former-conformed-name": "MCLEOD INC", "date-changed": "19960403"}}
===============================================================================

     As filed with the Securities and Exchange Commission on June 22, 2000

                                                  Registration No. 333-_________

                      SECURITIES AND EXCHANGE COMMISSION
                            Washington, D.C.  20549
                              __________________
                                   FORM S-8

                            REGISTRATION STATEMENT
                                     UNDER
                          THE SECURITIES ACT OF 1933

                            McLEODUSA INCORPORATED
            ------------------------------------------------------
            (Exact name of registrant as specified in its charter)

            Deleware                                   42-1407240
---------------------------------        ------------------------------------
   (State or other jurisdiction          (I.R.S. employer identification no.)
of incorporation or organization)

                           McLeodUSA Technology Park
                       6400 C Street, SW, P.O. Box 3177
                         Cedar Rapids, Iowa 52406-3177
                         -----------------------------
                   (Address of principal executive offices)

                            McLeodUSA Incorporated
                        1996 Employee Stock Option Plan
        --------------------------------------------------------------
                           (Full title of the plan)

                                 Randall Rings
                 Vice President, General Counsel and Secretary
                            McLeodUSA Incorporated
                           McLeodUSA Technology Park
                       6400 C Street, SW, P.O. Box 3177
                         Cedar Rapids, Iowa 52406-3177
                                (319) 364-0000
-------------------------------------------------------------------------------
(Name, address and telephone number, including area code, of agent for service)

                        CALCULATION OF REGISTRATION FEE
Proposed                       Proposed
      Title of securities        Amount to be              maximum offering              maximum aggregate         Amount of
       to be registered           registered               price per share (1)           offering price (1)    registration fee (1)
-----------------------------------------------------------------------------------------------------------------------------------
Class A Common Stock, par
 value $.01                      100,000,000                  $23.6875                     $2,368,750,000             $625,350

===================================================================================================================================
(1)  Estimated pursuant to Rule 457(c) and (h) solely for purposes of
calculating the amount of the registration fee, based on the average of the high
and low prices per share of McLeodUSA Incorporated Class A Common Stock, par
value $.01 per share, on June 15, 2000, as reported on the Nasdaq National
Market.

This Registration Statement incorporates by reference the information contained
in earlier registration statements on Form S-8 filed by McLeodUSA Incorporated
(the "Company") with the Securities and Exchange Commission on January 9, 1998
(Registration No. 333-44025) and on July 9, 1996 (Registration No. 333-07809) to
the extent relating to the McLeodUSA Incorporated 1996 Employee Stock Option
Plan, as amended (the "Plan").

===============================================================================
EXPLANATORY NOTE

     As permitted by General Instruction E to the Form S-8, this Registration
Statement incorporates by reference the information contained in earlier
registration statements on Form S-8 filed by McLeodUSA Incorporated (the
"Company") with the Securities and Exchange Commission on January 9, 1998
(Registration No. 333-44025) and on July 9, 1996 (Registration No. 333-07809) to
the extent relating to the McLeodUSA Incorporated 1996 Employee Stock Option
Plan, as amended (the "Plan").  Pursuant to these earlier registration
statements on Form S-8, the Company has previously registered 67,200,000 shares
of Class A Common Stock (adjusted to reflect two stock splits, described below).

     The Plan was duly adopted and approved by the Board of Directors on March
28, 1996 and was duly approved by the stockholders of the Company on April 30,
1996.  On March 27, 1997, the Board of Directors of the Company approved and
adopted an amendment to Article 4 of the Plan to increase the number of shares
of Class A Common Stock available for issuance thereunder to 225,000,000
(adjusted to reflect two stock splits, described below).  The Company's
stockholders approved such amendment to the Plan at the annual meeting of
stockholders held on May 29, 1997.

     The Company announced on June 30, 1999 a two-for-one stock split to be
effected in the form of a stock dividend.  The record date for the stock split
was July 12, 1999.  Stockholders of record at the market close on that date
received one additional share of Class A Common Stock for each share held.
Distribution of the additional shares took place on July 26, 1999.  In
connection with this stock dividend, the Company made a proportionate adjustment
to the number and exercise price of the options outstanding on July 26, 1999.

     On February 29, 2000, the Company announced a three-for-one stock split to
be effected in the form of a stock dividend.  The record date for the stock
split was April 4, 2000.  Stockholders of record at market close on that date
received two additional shares of Class A Common Stock for each share held.
Distribution of the additional shares took place on April 24, 2000.  In
connection with this stock dividend, the Company made a proportional adjustment
to the number and exercise price of the options outstanding on April 24, 2000.

     The Board of Directors approved and adopted various amendments to the Plan
on October 30, 1997, December 19, 1997, March 26, 1998 and September 24, 1998.
On April 12, 2000, the Board of Directors of the Company approved and adopted,
subject to stockholder approval, amendments to the Plan.  The Company's
stockholders approved such Plan as amended at a meeting of stockholders held on
May 31, 2000.

     Except for the foregoing amendments, the Plan remains unchanged.

                                      -2-
PART II

              INFORMATION REQUIRED IN THE REGISTRATION STATEMENT
Item 8.  Exhibits.

  Exhibit
  Number                               Description
  ------                               -----------
4.1  McLeodUSA Incorporated 1996 Employee Stock Option Plan, as amended and
         restated, filed as Exhibit A to the Company's definitive proxy
         statement flied with the Commission on April 26, 2000 and incorporated
         herein by reference

    5.1  Opinion of Hogan & Hartson L.L.P.

   23.1  Consent of  Arthur Andersen LLP

   23.2  Consent of Hogan & Hartson L.L.P. (included in Exhibit 5.1).

   24.1  Power of Attorney (included on signature page).
-3-
SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, as amended, the
registrant certifies that it has reasonable grounds to believe that it meets all
of the requirements for filing on Form S-8 and has duly caused this registration
statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of Cedar Rapids, State of Iowa, as of June 22, 2000.

                            McLEODUSA INCORPORATED

                            By: /s/ Randall Rings
                                -----------------
                                Randall Rings
                                Vice President, General Counsel and Secretary

                               POWER OF ATTORNEY

     KNOW ALL MEN BY THESE PRESENTS, that each person whose signature appears
below constitutes and appoints Randall Rings as true and lawful attorney-in-
fact, with full power of substitution, for him and in his name, place and stead,
in any and all capacities, to sign any and all amendments to this registration
statement (including post-effective amendments), and to file the same, with all
exhibits thereto and other documents in connection therewith, with the
Securities and Exchange Commission, granting unto said attorney-in-fact and
agents full power and authority to do and perform each and every act and thing
requisite and necessary to be done in and about the premises, as fully to all
intents and purposes as he might or could do in person, hereby ratifying and
confirming all that said attorney-in-fact, or his substitute or substitutes, may
lawfully do or cause to be done by virtue hereof.

     Pursuant to the requirements of the Securities Act of 1933, as amended,
this registration statement has been signed by the following persons, in the
capacities indicated below, as of June 22, 2000.
Signature                                   Title
       ---------                                   -----
/s/ Clark E. McLeod                          Chairman, Chief Executive Officer
-------------------------------------------    and Director (Principal Executive
Clark E. McLeod                                Officer)

/s/ Richard A. Lumpkin                       Vice Chairman and Director
-------------------------------------------
Richard A. Lumpkin

/s/ Stephen C. Gray                          President and Chief Operating Officer;
-------------------------------------------  President and Chief Executive Officer-Local
Stephen C. Gray                              Services; Director

/s/ Roy A. Wilkens                           Chief Technology Officer; Chief Executive
-------------------------------------------  Officer and President-Data Services; Director
Roy A. Wilkens
-4-
/s/ Blake O. Fisher, Jr.                     Group Vice President and Director
-------------------------------------------
Blake O. Fisher, Jr.

/s/ J. Lyle Patrick                          Group Vice President and Chief Financial
-------------------------------------------  Officer (Principal Financial Officer and
J. Lyle Patrick                              Principal Accounting Officer)

/s/ Anne K. Bingaman                                             Director
-------------------------------------------
Anne K. Bingaman
/s/ Erskine B. Bowles                                            Director
-------------------------------------------
Erskine B. Bowles

/s/ Peter H.O. Claudy                                            Director
-------------------------------------------
Peter H.O. Claudy

/s/ Thomas M. Collins                                            Director
-------------------------------------------
Thomas M. Collins

                                                                 Director
-------------------------------------------
Robert J. Currey

/s/ Theodore R. Forstmann                                        Director
-------------------------------------------
Theodore R. Forstmann

/s/ Daniel R. Hesse                                              Director
-------------------------------------------
Daniel R. Hesse

/s/ James E. Hoffman                                             Director
-------------------------------------------
James E. Hoffman

/s/ Paul D. Rhines                                               Director
-------------------------------------------
Paul D. Rhines
-5-
EXHIBIT INDEX
Exhibit
Number                            Description
------                            -----------
4.1  McLeodUSA Incorporated 1996 Employee Stock Option Plan, as amended and
       restated, filed as Exhibit A to the Company's definitive proxy statement
       flied with the Commission on April 26, 2000 and incorporated herein by
       reference

  5.1  Opinion of Hogan & Hartson L.L.P.

 23.1  Consent of  Arthur Andersen LLP

 23.2  Consent of Hogan & Hartson L.L.P. (included in Exhibit 5.1).

 24.1  Power of Attorney (included on signature page).
-6-