Exhibit 5.1

+1 617 526 6000 (t)

+1 617 526 5000 (f)

wilmerhale.com

June 5, 2007

McLeodUSA Incorporated

One Martha’s Way

Hiawatha, Iowa 52233

Re: Registration Statement on Form S-1

Ladies and Gentlemen:

This opinion is furnished to you in connection with a Registration Statement on Form S-1 (File No. 333-141490) (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), for the registration of an aggregate of 12,333,750 shares of Common Stock, par value $0.01 per share (the “Shares”), of McLeodUSA Incorporated, a Delaware corporation (the “Company”), of which (i) up to 7,150,000 Shares will be issued and sold by the Company and (ii) the remaining 5,183,750 Shares will be issued and sold by certain stockholders of the Company (the “Selling Stockholders”) (including 1,608,750 Shares issuable upon exercise of over-allotment options granted by certain Selling Stockholders).

The Shares are to be sold by the Company and the Selling Stockholders pursuant to an underwriting agreement (the “Underwriting Agreement”) to be entered into by and among the Company, the Selling Stockholders and Deutsche Bank Securities Inc. and Jefferies & Company, Inc., as representatives of the several underwriters named in the Underwriting Agreement, the form of which has been filed as Exhibit 1.1 to the Registration Statement.

We are acting as counsel for the Company in connection with the sale by the Company and the Selling Stockholders of the Shares. We have examined signed copies of the Registration Statement as filed with the Commission. We have also examined and relied upon the Underwriting Agreement, minutes of meetings of the stockholders and the Board of Directors of the Company as provided to us by the Company, stock record books of the Company as provided to us by the Company, the Certificate of Incorporation and By-Laws of the Company, each as restated and/or amended to date, and such other documents as we have deemed necessary for purposes of rendering the opinions hereinafter set forth.

In our examination of the foregoing documents, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as copies, the authenticity of the originals of such latter documents and the legal competence of all signatories to such documents.

Our opinion in clause (ii) below, insofar as it relates to the Selling Stockholders’ shares being fully paid, is based solely on a certificate of the Chief Financial Officer of the Company

confirming the Company’s receipt of the consideration called for by the applicable resolutions authorizing the issuance of such shares.

We express no opinion herein as to the laws of any state or jurisdiction other than the state laws of the Commonwealth of Massachusetts, the General Corporation Law of the State of Delaware and the federal laws of the United States of America.

Based upon and subject to the foregoing, we are of the opinion that (i) the Shares to be issued and sold by the Company have been duly authorized for issuance and, when such Shares are issued and paid for in accordance with the terms and conditions of the Underwriting Agreement, such Shares will be validly issued, fully paid and nonassessable and (ii) the Shares to be sold by the Selling Stockholders have been duly authorized and are validly issued, fully paid and nonassessable.

Please note that we are opining only as to the matters expressly set forth herein, and no opinion should be inferred as to any other matters. This opinion is based upon currently existing statutes, rules, regulations and judicial decisions, and we disclaim any obligation to advise you of any change in any of these sources of law or subsequent legal or factual developments which might affect any matters or opinions set forth herein after the Registration Statement has been declared effective by the Commission.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act and to the use of our name therein and in the related Prospectus under the caption “Legal Matters.” In giving such consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

Very truly yours,

WILMER CUTLER PICKERING
HALE AND DORR LLP

By:	/s/ David A. Westenberg
	David A. Westenberg, a Partner

McLeodUSA INC S-1/A