EXHIBIT 99.6
                                                                    ------------

 
                            MCLEODUSA INCORPORATED
 
                             OFFER TO EXCHANGE ITS
                    8 3/8% SENIOR NOTES DUE MARCH 15, 2008
          WHICH HAVE BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933
                      FOR ANY AND ALL OF ITS OUTSTANDING
                    8 3/8% SENIOR NOTES DUE MARCH 15, 2008
 
TO OUR CLIENTS:
 
  Enclosed for your consideration is a Prospectus, dated        , 1998 (the
"Prospectus"), and a form of Letter of Transmittal (the "Letter of
Transmittal"), relating to the offer (the "Exchange Offer") of McLeodUSA
Incorporated (the "Company") to exchange its 8 3/8% Senior Notes due March 15,
2008, which have been registered under the Securities Act of 1933 (the "1998
Exchange Notes"), for any and all of its outstanding 8 3/8% Senior Notes due
March 15, 2008 (the "1998 Senior Notes"), upon the terms and subject to the
conditions described in the Prospectus and the Letter of Transmittal. The
Exchange Offer is being made in order to satisfy certain obligations of the
Company contained in the Registration Agreement dated as of March 16, 1998,
among the Company, Salomon Brothers Inc, Bear, Stearns & Co. Inc., Morgan
Stanley & Co. Incorporated and Chase Securities Inc.
 
  This material is being forwarded to you as the beneficial owner of the 1998
Senior Notes carried by us in your account but not registered in your name. A
TENDER OF SUCH 1998 SENIOR NOTES MAY ONLY BE MADE BY US AS THE HOLDER OF
RECORD AND PURSUANT TO YOUR INSTRUCTIONS.
 
  Accordingly, we request instructions as to whether you wish us to tender on
your behalf the 1998 Senior Notes held by us for your account, pursuant to the
terms and conditions set forth in the enclosed Prospectus and Letter of
Transmittal.
 
  Your instructions should be forwarded to us as promptly as possible in order
to permit us to tender the 1998 Senior Notes on your behalf in accordance with
the provisions of the Exchange Offer. The Exchange Offer will expire at 5:00
p.m., New York City time, on       , 1998, unless extended by the Company (the
"Expiration Date"). Any 1998 Senior Notes tendered pursuant to the Exchange
Offer may be withdrawn, subject to the procedures described in the Prospectus
and the Letter of Transmittal, at any time prior to the Expiration Date.
 
  If you wish to have us tender your 1998 Senior Notes, please so instruct us
by completing, executing and returning to us the instruction form included
with this letter. THE LETTER OF TRANSMITTAL IS FURNISHED TO YOU FOR
INFORMATION ONLY AND MAY NOT BE USED DIRECTLY BY YOU TO TENDER 1998 SENIOR
NOTES.

 
                         INSTRUCTIONS WITH RESPECT TO
                              THE EXCHANGE OFFER
 
  The undersigned acknowledge(s) receipt of your letter and the enclosed
material referred to therein, including the Prospectus and the accompanying
form of Letter of Transmittal, relating to the Exchange Offer made by
McLeodUSA Incorporated with respect to its 1998 Senior Notes.
 
  This will instruct you as to the action to be taken by you relating to the
Exchange Offer with respect to the 1998 Senior Notes held by you for the
account of the undersigned, upon and subject to the terms and conditions set
forth in the Prospectus and the Letter of Transmittal.
 
  The aggregate principal amount of the 1998 Senior Notes held by you for the
account of the undersigned is (fill in amount):
 
                     $ ___________________________________
 
                             of the 8 3/8% Senior
                           Notes due March 15, 2008
 
  With respect to the Exchange Offer, the undersigned hereby instructs you
(check appropriate box):
 
  [_]To TENDER the following 1998 Senior Notes held by you for the account of
     the undersigned (insert aggregate principal amount at maturity of 1998
     Senior Notes to be tendered, in integral multiples of $1,000):
 
                     $ ___________________________________
 
                             of the 8 3/8% Senior
                           Notes due March 15, 2008
 
  [_]NOT to tender any 1998 Senior Notes held by you for the account of the
     undersigned.
 
                                       2

 
  If the undersigned instructs you to tender the 1998 Senior Notes held by you
for the account of the undersigned, it is understood that you are authorized
to make, on behalf of the undersigned (and the undersigned, by its signature
below, hereby makes to you), the representations, warranties and agreements
contained in the Letter of Transmittal that are to be made with respect to the
undersigned as beneficial owner.
 
                                   SIGN HERE
 
Name of beneficial owner(s): __________________________________________________
 
Signature(s): _________________________________________________________________
 
Name(s) (please print): _______________________________________________________
 
Address: ______________________________________________________________________
 
Telephone Number: _____________________________________________________________
 
Taxpayer Identification or Social Security Number(s): _________________________
 
Date: _________________________________________________________________________
 
  None of the 1998 Senior Notes held by us for your account will be tendered
unless we receive written instructions from you to do so. Unless a specific
contrary instruction is given in the space provided, your signature(s) hereon
shall constitute an instruction to us to tender all the 1998 Senior Notes held
by us for your account.
 
                                       3