Exhibit 99.4 MCLEODUSA INCORPORATED OFFER TO EXCHANGE ITS [12%/11 1/2%] SENIOR NOTES DUE [JULY 15, 2008/MAY 1, 2009] WHICH HAVE BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933 FOR ANY AND ALL OF THE OUTSTANDING [12%/11 1/2] SENIOR NOTES DUE [JULY 15, 2008/MAY 1, 2009] OF CAPROCK COMMUNICATIONS CORP. TO OUR CLIENTS: Enclosed for your consideration is a Prospectus, dated ______ __, 2000 (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 [12%/11 1/2%] Senior Notes Due [July 15, 2008/May 1, 2009], which have been registered under the Securities Act of 1933 (the "McLeodUSA Notes"), for any and all of the outstanding [12%/11 1/2] Senior Notes Due [July 15, 2008/May 1, 2009] of CapRock Communications Corp., a Texas Corporation (the "CapRock 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 Agreement and Plan of Merger by and among the Company, Cactus Acquisition Corp., a Delaware corporation and wholly owned subsidiary of the Company, and CapRock Communications Corp., dated as of October 2, 2000. This material is being forwarded to you as the beneficial owner of the CapRock Notes carried by us in your account but not registered in your name. A TENDER OF SUCH CAPROCK 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 CapRock 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 CapRock 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 November __, 2000, unless extended by the Company (the "Expiration Date"). Any CapRock 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 CapRock 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 CAPROCK 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 the CapRock Notes. This will instruct you as to the action to be taken by you relating to the Exchange Offer with respect to the CapRock 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 CapRock Notes held by you for the account of the undersigned is (fill in amount): $ ---------------------------------------- of the [12%/11 1/2] Senior Notes due [July 15, 2008/May 1, 2009] With respect to the Exchange Offer, the undersigned hereby instructs you (check appropriate box): |_| To TENDER the following CapRock Notes held by you for the account of the undersigned (insert aggregate principal amount at maturity of CapRock Notes to be tendered, in integral multiples of $1,000): $ ---------------------------------------- of the [12%/11 1/2] Senior Notes due [July 15, 2008/May 1, 2009] |_| NOT to tender any CapRock Notes held by you for the account of the undersigned. If the undersigned instructs you to tender the CapRock 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 CapRock 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 CapRock Notes held by us for your account.