McLeodusa S-1 IPO registration

QuickLinks -- Click here to rapidly navigate through this document

Exhibit 3.1

THIRD AMENDED AND RESTATED
CERTIFICATE OF INCORPORATION
OF
McLEODUSA INCORPORATED

        McLeodUSA Incorporated, a corporation organized and existing under the laws of the State of Delaware (the "Corporation"), hereby certifies as follows:

        FIRST: The Corporation was originally incorporated under the name McLeod, Inc. on July 29, 1993 and its original Certificate of Incorporation was filed with the Secretary of State of the State of Delaware on the same date. The date of the filing of the Corporations's Amended and Restated Certificate of Incorporation was May 2, 1996. The date of the filing of the Corporation's Second Amended and Restated Certificate of Incorporation was April 12, 2002.

        SECOND: This Third Amended and Restated Certificate of Incorporation, which restates and integrates and further amends the provisions previously filed with the Secretary of State of the State of Delaware on May 2, 1996, May 29, 1997, March 30, 2000, June 13, 2000 and April 12, 2002, is authorized by and is being filed in connection with the Joint Prepackaged Plan of Reorganization of McLeodUSA Incorporated and Its Affiliate Debtors, dated October 19, 2005 (as such plan may be amended from time to time, the "Plan of Reorganization"), and was duly adopted pursuant to Sections 242, 245 and 303 of the General Corporation Law of the State of Delaware as set forth in Title 8 of the Delaware Code (the "DGCL"). The Plan of Reorganization was confirmed by order entered on December 16, 2005, by the United States Bankruptcy Court for the Northern District of Illinois.

        THIRD: The text of the Certificate of Incorporation of the Corporation hereby is amended and restated to read in its entirety as follows:

ARTICLE 1. NAME

        The name of the Corporation is McLeodUSA Incorporated.

ARTICLE 2. REGISTERED OFFICE AND AGENT

        The registered office of the Corporation shall be located at 1209 Orange Street, Wilmington, Delaware, 19801 in the County of New Castle. The registered agent of the Corporation at such address shall be The Corporation Trust Company.

ARTICLE 3. PURPOSE AND POWERS

        The purpose of the Corporation is to engage in any lawful act or activity for which corporations may be organized under the DGCL. The Corporation shall have all power necessary or convenient to the conduct, promotion or attainment of such acts and activities.

ARTICLE 4. CAPITAL STOCK

        4.1AUTHORIZED SHARES    

        The total number of shares of stock which the Corporation shall have authority to issue is 37,500,000 shares of Common Stock, each having a par value of $0.01.

        4.2REDEMPTION    

        Notwithstanding any other provision of this Certificate of Incorporation to the contrary, outstanding shares of stock of the Corporation shall always be subject to redemption by the

1

Corporation, by action of the Board of Directors, if in the judgment of the Board of Directors such action should be taken, pursuant to Section 151(b) of the DGCL or any other applicable provision of law, to the extent necessary to prevent the loss or to secure the renewal or reinstatement of any license or franchise from any governmental agency held by the Corporation or any of its subsidiaries to conduct any portion of the business of the Corporation or any of its subsidiaries, which license or franchise is conditioned upon some or all of the holders of the Corporation's stock possessing prescribed qualifications. The terms and conditions of such redemption shall be as follows:

        (A)  The redemption price of the shares to be redeemed pursuant to this Section 4.2 shall be determined by the Board of Directors and shall be equal to the Fair Market Value (as defined herein) of such shares or, if such shares were purchased by a Disqualified Holder (as defined herein) within one year of the Redemption Date (as defined herein), the lesser of (i) the Fair Market Value of such shares and (ii) the purchase price paid by such Disqualified Holder for such shares;

        (B)  At the election of the Corporation, the redemption price of such shares may be paid in cash, Redemption Securities (as defined herein) or any combination thereof;

        (C)  If fewer than all shares held by Disqualified Holders are to be redeemed, the shares to be redeemed shall be selected in such manner as shall be determined by the Board of Directors, which may include selection first of the most recently purchased shares thereof, selection by lot or selection in any other manner determined by the Board of Directors;

        (D)  At least 30 days' prior written notice of the Redemption Date shall be given to any Disqualified Holder of shares selected to be redeemed (unless waived in writing by any such holder), provided that the Redemption Date may be the date on which written notice shall be given to such holder if the cash or Redemption Securities necessary to effect the redemption shall have been deposited in trust for the benefit of such holder and subject to immediate withdrawal by it upon surrender of the stock certificates for the shares to be redeemed;

        (E)  From and after the Redemption Date, unless the Corporation shall have defaulted in paying or setting aside for payment the cash or Redemption Securities payable upon such redemption, any and all rights of whatever nature that any Disqualified Holder may have with respect to any shares selected for redemption (including without limitation any rights to vote or participate in dividends declared on stock of the same class or series as such shares) shall cease and terminate, and such Disqualified Holder shall thenceforth be entitled only to receive, with respect to such shares, the cash or Redemption Securities payable upon redemption; and

        (F)  Such additional terms and conditions as the Board of Directors shall determine.

        For purposes of this Section 4.2, the following terms shall have the meanings indicated:

        "Disqualified Holder" shall mean any holder of shares of stock of the Corporation whose holding of such stock, either individually or when taken together with the holding of shares of stock of the Corporation by any other holders, may result, in the judgment of the Board of Directors, in the loss of, or the failure to secure the renewal or reinstatement of, any license or franchise from any governmental agency held by the Corporation or any of its subsidiaries to conduct any portion of the business of the Corporation or any of its subsidiaries.

        "Fair Market Value" of a share of the Corporation's stock of any class or series shall mean the average Closing Price (as defined herein) for such a share for each of the 45 most recent days on which shares of stock of such class or series shall have been traded preceding the day on which notice of redemption shall be given pursuant to paragraph (D) of this Section 4.2; provided, however, that if shares of stock of such class or series are not traded on any securities exchange or in the over-the-counter market, "Fair Market Value" shall be

2

determined by the Board of Directors in good faith. "Closing Price" on any day means the reported closing sales price or, in case no such sale takes place, the average of the reported closing bid and asked prices on the principal United States securities exchange registered under the Securities Exchange Act of 1934, as amended, on which such stock is listed, or, if such stock is not listed on any such exchange, the highest closing sales price or bid quotation for such stock on the National Association of Securities Dealers, Inc. Automated Quotations System or any system then in use, or if no such prices or quotations are available, the fair market value on the day in question as determined by the Board of Directors in good faith.

        "Redemption Date" shall mean the date fixed by the Board of Directors for the redemption of any shares of stock of the Corporation pursuant to this Section 4.2.

        "Redemption Securities" shall mean any debt or equity securities of the Corporation, any of its subsidiaries or any other corporations, or any combination thereof, having such terms and conditions as shall be approved by the Board of Directors and which, together with any cash to be paid as part of the redemption price, in the opinion of any investment banking firm selected by the Board of Directors (which may be a firm which provides other investment banking, brokerage or other services to the Corporation), has a value, at the time notice of redemption is given pursuant to paragraph (D) of this Section 4.2, at least equal to the price required to be paid pursuant to paragraph (A) of this Section 4.2 (assuming for purposes of such valuation, in the case of Redemption Securities to be publicly traded, such Redemption Securities were fully distributed and trading under normal conditions).

ARTICLE 5. BOARD OF DIRECTORS

        5.1DIRECTORS; NUMBER; ELECTION    

        The number of directors of the Corporation shall be such number as from time to time shall be fixed by, or in the manner provided in, the Bylaws of the Corporation. Notwithstanding anything in the Bylaws of the Corporation to the contrary, the number of directors and initial terms of such directors shall not be inconsistent with the terms of the Plan of Reorganization.

        Unless and except to the extent that the Bylaws of the Corporation shall otherwise require, the election of directors of the Corporation need not be by written ballot.

        In addition to the powers and authority hereinbefore or by statute expressly conferred upon them, the directors are hereby empowered to exercise all such powers and do all such acts and things as may be exercised or done by the Corporation, subject, nevertheless, to the provisions of the DGCL, this Third Amended and Restated Certificate of Incorporation, and any Bylaws adopted in accordance with the provisions hereof and thereof; provided, however, that no Bylaws hereafter adopted shall invalidate any prior act of the directors which would have been valid if such Bylaws had not been adopted.

        5.2MANAGEMENT OF BUSINESS AND AFFAIRS OF THE CORPORATION    

        The business and affairs of the Corporation shall be managed by or under the direction of the Board of Directors.

        5.3LIMITATION OF LIABILITY    

        No director of the Corporation shall be personally liable to the Corporation or any of its stockholders for monetary damages for breach of fiduciary duty as a director, except for liability (a) for any breach of the director's duty of loyalty to the Corporation or its stockholders; (b) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law; (c) under Section 174 of the DGCL; or (d) for any transaction from which the director derived an improper personal benefit. Any repeal or modification of this Section 5.3 shall not adversely affect any

3

right or protection of a director of the Corporation existing at the time of such repeal or modification with respect to acts or omissions occurring prior to such repeal or modification.

ARTICLE 6. INDEMNIFICATION

        The Corporation shall indemnify its directors and officers who serve in such capacity after the effective date of the Plan of Reorganization to the fullest extent authorized or permitted by law, as now or hereafter in effect, and such right to indemnification shall continue as to a person who has ceased to be a director or officer of the Corporation on or after the effective date of the Plan of Reorganization and shall inure to the benefit of his or her heirs, executors and personal and legal representatives; provided, however, that, except for proceedings to enforce rights to indemnification, the Corporation shall not be obligated to indemnify any director or officer (or his or her heirs, executors or personal or legal representatives) in connection with a proceeding (or part thereof) initiated by such person unless such proceeding (or part thereof) was authorized or consented to by the Board of Directors. The right to indemnification conferred by this Article 6 shall include the right to be paid by the Corporation the expenses incurred in defending or otherwise participating in any proceeding in advance of its final disposition to the extent authorized or permitted by law, as now or hereafter in effect.

        The Corporation may, to the extent authorized from time to time by the Board of Directors, provide rights to indemnification and to the advancement of expenses to employees and agents of the Corporation similar to those conferred in this Article 6 to directors and officers of the Corporation.

        The rights to indemnification and to the advance of expenses conferred in this Article 6 shall not be exclusive of any other right which any person may have or hereafter acquire under this Certificate of Incorporation, the Bylaws of the Corporation, any statute, agreement, vote of stockholders or disinterested directors or otherwise.

        Notwithstanding anything in this Certificate of Incorporation or the Bylaws of the Corporation, the Corporation shall not indemnify any person who resigned as or otherwise ceased to be a director or officer on or prior to the effective date of the Plan of Reorganization.

        Any repeal or modification of this Article 6 by the stockholders of the Corporation shall not adversely affect any rights to indemnification and to the advancement of expenses of a director or officer of the Corporation existing at the time of such repeal or modification with respect to any acts or omissions occurring prior to such repeal or modification.

ARTICLE 7. SECTION 203 OF THE DGCL

        The Corporation expressly elects not to be governed by Section 203 of the DGCL, as the same may be amended from time to time.

ARTICLE 8. STOCKHOLDERS AGREEMENT

        Any transfer of stock of the Corporation not in compliance with the New Stockholders Agreement (as defined in the Plan of Reorganization), as amended from time to time, shall be null and void.

ARTICLE 9. AMENDMENT OF CERTIFICATE OF INCORPORATION

        The Corporation reserves the right to amend, alter, change or repeal any provision contained in this Third Amended and Restated Certificate of Incorporation, in the manner now or hereafter prescribed by statute, and all rights conferred upon stockholders herein are granted subject to this reservation.

4

ARTICLE 10. AMENDMENT OF BYLAWS

        The Bylaws of the Corporation may be altered, amended or repealed, or new bylaws may be made, by the stockholders in accordance with Section 2.10 of the Bylaws of the Corporation, or by the Board of Directors, except with respect to (a) Section 3.3 of the Bylaws of the Corporation, which shall require the vote of 2/3 of the stockholders in order to alter, amend or repeal and (b) Sections 3.5 and 3.6 of the Bylaws of the Corporation, which, until the second anniversary of the effective date of the Plan of Reorganization, shall require the vote of 2/3 of the stockholders in order to alter, amend or repeal.

ARTICLE 11. ADDITIONAL PROVISIONS

        The Corporation will not issue non-voting equity securities to the extent prohibited by Section 1123(a)(6) of the United States Bankruptcy Code (the "Bankruptcy Code") as in effect on the effective date of the Plan of Reorganization;provided,however, that this Article 11: (a) will have no further force and effect beyond that required under Section 1123 of the Bankruptcy Code; (b) will have such force and effect, if any, only for so long as such Section is in effect and applicable to the Corporation; and (c) in all events may be amended or eliminated in accordance with applicable law as from time to time in effect.

        IN WITNESS WHEREOF, McLeodUSA Incorporated has caused this Third Amended and Restated Certificate of Incorporation to be signed and attested by its duly authorized officers this 6th day of January, 2006.

MCLEODUSA INCORPORATED
By:	/s/  JAMES E. THOMPSON      Name: James E. Thompson Title: Secretary

5

QuickLinks

Exhibit 3.1