BOARD MEMBERSHIP AGREEMENT

Exhibit 10.3

BOARD MEMBERSHIP AGREEMENT

BOARD MEMBERSHIP AGREEMENT, dated as of February 8, 2008 (this “Agreement”), among PAETEC Holding Corp., a Delaware corporation (“Parent”), each Person listed on the signature pages hereof under the heading “Fidelity Stockholders” (collectively and as more fully defined below, the “Fidelity Stockholders”), and each Person listed on the signature pages hereof under the heading “Wayzata Stockholders” (collectively and as more fully defined below, the “Wayzata Stockholders”);

WHEREAS, as of the date hereof (the “Effective Date”), Parent has consummated a merger transaction pursuant to which the common stock, par value $0.01 per share, of McLeodUSA Incorporated (the “Seller Common Stock”) held by the Fidelity Stockholders has been converted into the right to receive 12,185,815 shares of common stock, par value $0.01 per share, of Parent (the “Parent Common Stock”) and the Seller Common Stock held by the Wayzata Stockholders has been converted into the right to receive 11,477,800 shares of the Parent Common Stock; and

WHEREAS, Parent, the Fidelity Stockholders and the Wayzata Stockholders wish to enter into this Agreement to set forth their mutual agreement with respect to the board membership and board observer rights provided for herein;

NOW, THEREFORE, in consideration of the foregoing and the mutual promises and agreements contained herein, the parties hereto agree as follows:

ARTICLE I

DEFINITIONS

SECTION 1.1. Definitions. As used in this Agreement, the following terms have the meanings set forth below:

“Affiliate” has the same meaning as in Rule 12b-2 promulgated under the Exchange Act as in effect on the date hereof.

“Beneficial owner” and to “beneficially own” has the same meaning as in Rule 13d-3 promulgated under the Exchange Act as in effect on the date hereof; provided that a Person shall not be deemed to be the beneficial owner of any Parent Common Stock solely because such Person is a party to this Agreement, if such Person would not be deemed to be the beneficial owner of such Parent Common Stock within the meaning of such Rule 13d-3 if such Person were not a party to this Agreement.

“Board of Directors” means the Board of Directors of Parent.

“Director” means a member of the Board of Directors.

“Exchange Act” means the Securities Exchange Act of 1934, as amended, and the rules and regulations promulgated thereunder.

-1-

“Fidelity Board Observer Period” means the period beginning on the Effective Date and expiring on the earlier to occur of (a) the date on which the Fidelity Stockholders collectively shall cease to own of record and beneficially at least 6,092,907 Merger Shares, as such number of Merger Shares shall be proportionately adjusted in connection with any stock split, stock dividend, reverse stock split or other combination, reclassification or other similar event affecting the Parent Common Stock, and (b) February 8, 2010.

“Fidelity Stockholders” means the Persons listed on the signature pages hereof under the heading “Fidelity Stockholders” and any other Affiliate of FMR Corp. advised by FMR Corp.

“Merger” means the merger consummated on the Effective Date pursuant to the Merger Agreement.

“Merger Agreement” means the Agreement and Plan of Merger, dated as of September 17, 2007, as amended from time to time, among Parent, PS Acquisition Corp., a wholly-owned subsidiary of Parent, and McLeodUSA Incorporated.

“Merger Shares” means the Parent Common Stock issued by Parent in the Merger pursuant to the Merger Agreement to the Fidelity Stockholders or the Wayzata Stockholders, as the case may be.

“Person” means any individual, corporation, partnership, limited liability company, limited partnership, joint venture, association, joint-stock company, trust, unincorporated organization or government body.

“Wayzata Board Membership Period” means the period beginning on the day following the Effective Date and, subject to Section 2.2(a), expiring on the earliest to occur of (a) the date on which the Wayzata Stockholders collectively shall cease to own of record and beneficially at least 5,738,900 Merger Shares, as such number of Merger Shares shall be proportionately adjusted in connection with any stock split, stock dividend, reverse stock split or other combination, reclassification or other similar event affecting the Parent Common Stock, (b) February 8, 2010 and (c) March 24, 2008, but only if the Wayzata Stockholders shall not have made an initial designation pursuant to Section 2.1 on or before March 24, 2008.

“Wayzata Stockholders” means the Persons listed on the signature pages hereof under the heading “Wayzata Stockholders” and any Affiliate of Wayzata Investment Partners LLC.

ARTICLE II

SECTION 2.1. Designation of Director. During the Wayzata Board Membership Period, the Wayzata Stockholders collectively shall be entitled to designate one individual for appointment or for nomination for election to the Board of Directors who shall be reasonably acceptable to Parent. Any such designation shall be made in writing and addressed to the Board of Directors. The designee identified in the initial designation pursuant to this Section 2.1 shall be appointed to Class III of the Board of Directors with a term expiring at Parent’s annual meeting of stockholders in 2009.

-2-

SECTION 2.2. Vacancies Resignations.

(a) Subject to Section 2.2(b), during the Wayzata Board Membership Period, in the event that a vacancy is created at any time by the death, disability, retirement, resignation or removal of the Director designated for appointment or for nomination for election to the Board of Directors pursuant to Section 2.1, the Wayzata Stockholders shall collectively have the right, by written notice to Parent, to designate a replacement individual for appointment or nomination for election to the Board of Directors to fill such vacancy. Each such replacement designee shall be reasonably acceptable to Parent. If the Wayzata Stockholders do not designate any such replacement to fill such vacancy within 30 days after receipt by the Wayzata Stockholders of written notice from Parent that the Wayzata Stockholders have 30 days to designate a replacement to fill such vacancy, the Board of Directors shall be entitled to fill such vacancy or to reduce the number of authorized Directors by one, and the Wayzata Stockholders thereafter shall not have any rights to designate a Director pursuant to this Agreement. The Director appointed or elected to the Board of Directors pursuant to a designation made by Wayzata Stockholders in accordance with this Section 2.2(a) shall be deemed for purposes of this Article II to be a Director who was designated for appointment or nomination for election to the Board of Directors pursuant to Section 2.1.

(b) Promptly upon the expiration of the Wayzata Board Membership Period, the Wayzata Stockholders shall take all necessary actions (including actions as stockholders of Parent) to cause the Director they have previously designated for appointment or nomination for election to the Board of Directors pursuant to Section 2.1 to resign from the Board of Directors as soon as reasonably practicable.

SECTION 2.3. Action by Wayzata Stockholders. All communications by and to the Wayzata Stockholders relating to the exercise of their rights pursuant to Sections 2.1 and 2.2 shall be directed to and by a single representative of the Wayzata Stockholders designated in writing by the Wayzata Stockholders to Parent from time to time. Parent may rely upon any such designation that is executed and delivered by Wayzata Stockholders that collectively own of record and beneficially at least a majority of the Merger Shares then owned of record and beneficially by all Wayzata Stockholders. The initial representative of the Wayzata Stockholders shall be John D. McEvoy.

SECTION 2.4. Undertaking By Parent. During the Wayzata Board Membership Period, Parent agrees to take such action as shall be necessary to cause each individual designated by the Wayzata Stockholders pursuant to Section 2.1 to be appointed as a Director or to be nominated for election by Parent’s stockholders as a Director, including, without limitation, having such individual named as a management nominee for whom proxies would be solicited for the management slate.

ARTICLE III

BOARD OBSERVER RIGHTS

SECTION 3.1. Board Observer Rights. During the Fidelity Board Observer Period, the Fidelity Stockholders shall have the right to appoint one representative (the

-3-

“Observer Representative”) to attend each meeting of the Board of Directors as a non-voting observer, whether such meeting is conducted in person or by teleconference. Any such designation shall be made in writing and addressed to the Board of Directors. The Observer Representative shall have the right to present matters for consideration by the Board of Directors and to speak on matters presented by others. Subject to the confidentiality provisions of Section 3.2, Parent shall cause the Observer Representative to be provided with all communications and materials that are provided by Parent or its consultants to the members of the Board of Directors generally, including all notices, board packages, reports, presentations, minutes and consent instruments. The Fidelity Stockholders may change the Observer Representative from time to time during the Fidelity Board Observer Period upon written notice to Parent, provided that each Observer Representative appointed from time to time shall be reasonably acceptable to Parent. Parent shall reimburse the Observer Representative or the Fidelity Stockholders for the reasonable out-of-pocket travel expenses of the Observer Representative in attending meetings of the Board of Directors.

SECTION 3.2. Confidentiality. Notwithstanding any provision of Section 3.1 to the contrary, the Board of Directors shall have the right to keep confidential from the Observer Representative for such period of time as the Board of Directors deems reasonable any information and copies of written materials Parent is required by law or agreement with a third party to keep confidential. As a condition of the exercise of his rights under this Section 3.1, the Observer Representative shall enter into such agreements or undertakings with Parent to maintain the confidentiality of information provided to him in connection with the exercise of such rights as Parent may reasonably request.

SECTION 3.3. Action by Fidelity Stockholders. All communications by and to the Fidelity Stockholders relating to the exercise of their rights pursuant to Section 3.1 shall be directed to and by a single representative of the Fidelity Stockholders designated in writing by the Fidelity Stockholders to Parent from time to time. Parent may rely upon any such designation that is executed and delivered by Fidelity Stockholders that collectively own of record and beneficially at least a majority of the Merger Shares then owned of record and beneficially by all Fidelity Stockholders. The initial representative of the Fidelity Stockholders shall be Nate Van Duzer.

ARTICLE IV

MISCELLANEOUS

SECTION 4.1. Notices. All notices, requests, claims, demands and other communications hereunder shall be in writing and shall be given (and shall be deemed to have been duly received if so given) by facsimile, hand delivery, by mail (registered or certified mail, postage prepaid, return receipt requested) or by any overnight courier service, such as Federal Express, providing proof of delivery. All communications hereunder shall be delivered to the respective parties at the following addresses:

-4-

if to the Wayzata Stockholders, to their representative

designated pursuant to Section 2.3, as follows:

Wayzata Investment Partners LLC