QuickLinks -- Click here to rapidly navigate through this document

Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

        We consent to the incorporation by reference in Registration Statement No. 33-100118 on Form S-8 of our reports dated March 25, 2005, relating to the consolidated financial statements and financial statement schedule of McLeodUSA Incorporated (which report includes explanatory paragraphs relating to substantial doubt of the Company's ability to continue as a going concern and the application of AICPA Statement of Position 90-7, "Financial Reporting for Entities in Reorganization Under the Bankruptcy Code") and management's report on the effectiveness of internal control over financial reporting, appearing in the Annual Report on Form 10-K of McLeodUSA Incorporated for the year ended December 31, 2004.

/s/ DELOITTE & TOUCHE LLP
Dallas, Texas
March 25, 2005

QuickLinks

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM