EMPLOYMENT AGREEMENT

QuickLinks -- Click here to rapidly navigate through this document

Exhibit 10.4

EMPLOYMENT AGREEMENT

        THIS AGREEMENT is by and between McLeodUSA, Inc. (the "Company"), and Royce J. Holland (the "Executive"), dated as of January 1, 2006 and effective as of the date hereof (the "Effective Date").

        WHEREAS, the Company desires to have the association and services of the Executive in order to obtain the Executive's experience, skills, abilities, background and knowledge, desires to provide incentive to the Executive to provide valuable future services to the Company, and is willing to employ the Executive in the capacities and on the terms and conditions set forth in this Agreement; and

        WHEREAS, the Company wishes to provide for contractual terms relating to the employment by the Company of the Executive from and after the Effective Date; and

        WHEREAS, the Executive wishes to serve the Company, in the capacities and on the terms and conditions set forth in this Agreement and is willing to accept such employment on the terms and conditions set forth in this Agreement.

        NOW, THEREFORE, it is hereby agreed as follows:

        1.      TERM.    The term of this Agreement shall commence on the Effective Date and end on the date four years following the Effective Date unless sooner terminated pursuant to Section 4 of this Agreement (the "Term").

        2.      POSITION AND DUTIES.    

        (a)   During the Term, the Executive shall serve as the Chief Executive Officer of the Company and as a member the Company's Board of Directors (the "Board"), in each case with such duties and responsibilities as are customarily assigned to these positions, and such other duties and responsibilities not inconsistent therewith as may from time to time be assigned to him by the Board. During the Term, the Company shall cause the Executive to be included in the slate of persons nominated to serve as members of the Board and shall use its best efforts (including, without limitation, the solicitation of proxies) to have the Executive elected and reelected to the Board.

        (b)   During the Term, and excluding any periods of vacation and sick leave to which the Executive is entitled, the Executive shall devote his full business attention and time to the business and affairs of the Company and shall use all reasonable efforts to carry out his responsibilities faithfully and efficiently. However, the Executive may, subject to the prior approval of the Board, serve on corporate boards and such industry, civic or charitable boards or committees as Executive may determine, so long as these activities do not interfere or represent a conflict of interest with the performance of the Executive's responsibilities to the Company.

        (c)   During the Term, the Executive shall be based at the Company's principal executive offices except for travel reasonably required for the performance of Executive's duties hereunder. The Executive and the Board shall select a location for the Company's principal executive offices, with such location being within the Company's market area.

        3.      COMPENSATION.    

        (a)      BASE SALARY.    The Company shall pay the Executive an annual base salary (the "Annual Base Salary") of $500,000. The Annual Base Salary shall be paid in accordance with the Company's regular payroll practice for its senior executives, as in effect from time to time. Annual Base Salary shall be reviewed at least annually by the Board and may from time to time be increased (but not decreased) as determined by the Board. Effective as of the date of any such increase the Annual Base Salary as so increased shall be considered the new Annual Base Salary for all purposes of this Agreement and may not thereafter be reduced. Any increase in Annual

Base Salary shall not limit or reduce any other obligation of the Company to the Executive under this Agreement. No additional remuneration shall be paid to Executive with respect to his service on the Board during the Term.

        (b)      ANNUAL CASH BONUS.    During the Term, the Executive shall participate in annual cash incentive compensation plans, in effect or to be adopted and approved by the Board or its Compensation Committee from time to time, with applicable corporate and individual performance targets and maximum award amounts determined by the Compensation Committee. The Executive's annual target bonus opportunity pursuant to such plans shall be 100% of the Annual Base Salary in effect for the Executive at the beginning of the year, provided that the Executive's bonus payment for any particular year may be more or less than the foregoing target bonus opportunity, based on the level of achievement of the applicable performance targets. Any cash bonuses payable to the Executive will be paid at the time the Company normally pays such bonuses to its senior executives and will be subject to the terms and conditions of the applicable annual cash incentive compensation plan.

        (c)      OPTION GRANT.    As soon as practicable following the Effective Date, the Company shall adopt an equity compensation plan (the "Equity Plan") which shall provide for the grant of stock options and restricted stock grants. Upon the adoption of the Equity Plan (which shall be developed by Executive and the Board of Directors), the Company shall grant to the Executive an award of stock options thereunder with respect to a number of shares equal to 1.5% of the total number of shares of Company common stock outstanding immediately prior to such award (and the award of restricted stock described below). The option grant shall provide that it shall become vested and exercisable with respect to 25% of the shares subject thereto on each of the Effective Date and the first three anniversaries of the Effective Date, subject to the Executive's continued employment with the Company on such anniversary dates, and shall provide for a per-share exercise price equal to the fair market value of the underlying shares. For example, it is anticipated that there will be 30 million shares outstanding at the time of the option grant and that the equity value of the Company will be $250 million at such time. If that is the case, there would be 450,000 shares subject to the option and the per-share exercise price applicable to the option would be $8.33.

        In addition, upon the adoption of the Equity Plan, the Company shall grant to the Executive an award of performance vesting stock options thereunder with respect to a number of shares equal to 1.0% of the total number of shares of Company common stock outstanding immediately prior to such award (and prior to the award of any other options or restricted stock). The performance vesting option grant shall provide that it becomes vested and exercisable with respect to 50% of the shares subject thereto upon completion of an initial public offering of Company common stock or a Change in Control as defined in Paragraph 3(e) hereof, and with respect to the other 50% of the shares subject thereto if the value of the Company's equity is at least $500 million at the completion of a Change in Control or initial public offering (disregarding the value of any equity issued after the Effective Date in connection with any corporate acquisitions or similar transactions). The option grant shall provide for a per-share exercise price equal to that of the time vested option grant discussed above in this paragraph 3(c). All performance vesting cliffs are subject to the Executive's continued employment with the Company on the date of such events. If Executive's employment is terminated by the Company for Cause or by Executive without Good Reason prior to the first anniversary of the Effective Date, Executive will forfeit all vested options of any type and will return to the Company any shares acquired pursuant to their exercise.

        (d)      RESTRICTED STOCK GRANT.    As soon as practicable following the Effective Date, the Company shall grant to the Executive an award of restricted stock pursuant to the Equity Plan with respect to a number of shares equal to 1.5% of the total number of shares of Company common stock outstanding immediately prior to such award (and the award of options described above). The restricted grant shall provide that it shall become vested and no longer subject to forfeiture (except as provided in this paragraph below) with respect to 25% of the shares subject thereto on the Effective Date and each of the first three anniversaries of the Effective Date,

subject to the Executive's continued employment with the Company on such anniversary dates. In addition, Company shall grant to the Executive an award of performance vesting restricted stock equal to 1.0% of the total number of shares of Company common stock outstanding immediately prior to such award (and prior to the award of options described above), with vesting criteria identical to the performance vesting stock option grant described in Paragraph 3(c) hereof. If Executive's employment is terminated by the Company for Cause or by Executive without Good Reason prior to the first anniversary of the Effective Date, Executive will forfeit all vested restricted stock.

        (e)      OTHER PROVISIONS WITH RESPECT TO EQUITY AWARDS.    Each of the option and restricted stock awards described in Sections 3(c) and 3(d) shall be subject to the terms of the Equity Plan and an award agreement which shall include the terms and conditions set forth in such sections. In addition, each of the option and restricted stock awards described in Sections 3(c) and 3(d) shall provide that the award shall become fully vested immediately upon a "Change in Control" of the Company. Notwithstanding the immediately preceding sentence, the performance vesting stock options described in the second paragraph of Section 3(c) and the performance vesting restricted stock described in Section 3(d) shall vest according to the language in Sections 3(c) and 3(d). Additional grants of stock options or restricted stock may be made during the Term to the Executive by the Board (or a committee thereof), in its discretion. For purposes of this Agreement, a "Change in Control" shall be deemed to have occurred if any Person is or becomes the Beneficial Owner, directly or indirectly, of securities of the Company representing more than 50% of either the then outstanding shares of common stock of the Company or the combined voting power of the Company's then outstanding securities. Notwithstanding anything in the foregoing to the contrary, no Change in Control shall be deemed to have occurred for purposes of this Agreement by virtue of any transaction which results in the Executive, or a group of Persons which includes the Executive, acquiring, directly or indirectly, 50% or more of either the then outstanding shares of common stock of the Company or the combined voting power of the Company's then outstanding securities. For purposes of the preceding definition of Change in Control, the following definitions shall apply: (1) "Beneficial Owner" shall have the meaning set forth in Rule 13d-3 under the Exchange Act; (2) "Exchange Act" shall mean the Securities Exchange Act of 1934, as amended from time to time; and (3) "Person" shall have the meaning given in Section 3(a)(9) of the Exchange Act, as modified and used in Sections 13(d) and 14(d) thereof, except that such term shall not include (i) the Company or any of its subsidiaries, (ii) a trustee or other fiduciary holding securities under an employee benefit plan of the Company or any of its Affiliates, (iii) an underwriter temporarily holding securities pursuant to an offering of such securities and (iv) a corporation owned, directly or indirectly, by the stockholders of the Company in substantially the same proportions as their ownership of stock of the Company.

        (f)      EQUITY PLAN.    Executive shall work with the Board to develop the Equity Plan at the earliest practical date. With regard to stock options and restricted stock, the Equity Plan shall include the following provisions: (1) stock options shall have a term of six years, unless at the expiration of the six-year period, the common stock of the Company is not publicly traded, in which event the length of the option will be the earlier of ten years from issuance or three months following the date that the Company's common stock becomes publicly traded; (2) if Executive's (or other directors and officers subject to the Equity Plan) employment terminates for any reason, Executive, or such directors and officers shall have three months following termination of employment (but not beyond the maximum term of the option) to exercise vested stock options if the Company's common stock is publicly traded, or if the Company's common stock is not publicly traded at the date of termination of employment, three months following the date that the Company's common stock begins to be publicly traded or ten years from issuance, whichever is earlier (but in no event beyond the maximum term of the option); (3) if Company's common stock is not publicly traded, Executive, Directors and Officers may sell vested restricted stock in a private transaction subject to a right of first refusal by the Company (however, the Company shall have no obligation to buy back such stock); and (4) other provisions as the Executive and Board shall decide.

        (g)      OTHER BENEFITS.    During the Term, the Executive shall be eligible to participate in the retirement, welfare benefit, and fringe benefit plans, practices, policies and programs of the Company (including any medical, prescription, dental, disability, life insurance, accidental death and travel accident insurance plans and programs) to the same extent, and subject to the same terms and conditions, as t