Exhibit 5.1

[Letterhead of Hogan Lovells US LLP]

June 10, 2011

Board of Directors

PAETEC Holding Corp.

One PAETEC Plaza

600 Willowbrook Office Park

Fairport, NY 14450

Ladies and Gentlemen:

We are acting as counsel to PAETEC Holding Corp., a Delaware corporation (the “Company”), in connection with its registration statement on Form S-1, as amended (the “Registration Statement”), filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Act”), relating to the proposed offer and sale of:

This opinion letter is furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R. § 229.601(b)(5), in connection with the Registration Statement.

1

Board of Directors

PAETEC Holding Corp.

For purposes of this opinion letter, we have examined copies of such agreements, instruments and documents as we have deemed an appropriate basis on which to render the opinions hereinafter expressed. In our examination of the aforesaid documents, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the accuracy and completeness of all documents submitted to us, the authenticity of all original documents, and the conformity to authentic original documents of all documents submitted to us as copies (including telecopies). As to all matters of fact, we have relied on the representations and statements of fact made in the documents so reviewed, and we have not independently established the facts so relied on. This opinion letter is given, and all statements herein are made, in the context of the foregoing.

For purposes of this opinion letter, we have assumed that (i) the issuance, sale, amount and terms of any 2011 Plan Warrants to be offered from time to time will have been duly authorized and established by proper action of the board of directors of the Company or a duly authorized committee of such board (“Board Action”) consistent with the procedures and terms described in the 2011 Agent Plan and in accordance with the Company’s certificate of incorporation and bylaws and applicable Delaware corporate law, in a manner that does not violate any law, government or court-imposed order or restriction or agreement or instrument then binding on the Company or otherwise impair the legal or binding nature of the obligations represented by the 2011 Plan Warrants; (ii) at the time of offer, issuance and sale of any Securities, the Registration Statement will have been declared effective under the Act, and no stop order suspending its effectiveness will have been issued and remain in effect; and (iii) the Company will remain a Delaware corporation.

This opinion letter is based as to matters of law solely on the applicable provisions of the following, as currently in effect: (1) as to the opinions given in paragraphs (i), (ii) and (iii), the Delaware General Corporation Law, as amended; and (2) as to the opinion given in paragraph (iv), the laws of the State of New York (but not including any laws, statutes, ordinances, administrative decisions, rules or regulations of any political subdivision below the state level). We express no opinion herein as to any other laws, statutes, ordinances, rules, or regulations (and in particular, we express no opinion as to any effect that such other laws, statutes, ordinances, rules, or regulations may have on the opinions expressed herein). As used herein, the term “Delaware General Corporation Law, as amended” includes the statutory provisions contained therein, all applicable provisions of the Delaware Constitution and reported judicial decisions interpreting these laws.

Based upon, subject to and limited by the foregoing, we are of the opinion that:

(i)    following (a) issuance of the 2011 Plan Shares pursuant to the terms of the 2011 Agent Plan and of the warrant certificates evidencing the 2011 Plan Warrants thereunder and (b) receipt by the Company of the consideration for the 2011 Plan Shares specified in the applicable Board Action and in the 2011 Agent Plan and the warrant certificates evidencing the 2011 Plan Warrants thereunder, the 2011 Plan Shares will be validly issued, fully paid and nonassessable;

(ii)    following (a) issuance of the 2009 Plan Shares pursuant to the terms of the 2009 Agent Plan and of the warrant certificates evidencing the 2009 Plan Warrants thereunder and (b) receipt by the Company of the consideration for the 2009 Plan Shares specified in the applicable

2

Board of Directors

PAETEC Holding Corp.

Board Action and in the 2009 Agent Plan and the warrant certificates evidencing the 2009 Plan Warrants thereunder, the 2009 Plan Shares will be validly issued, fully paid and nonassessable;

(iii)    following (a) issuance of the 1999 Plan Shares pursuant to the terms of the 1999 Agent Plan and of the warrant certificates evidencing the 1999 Plan Warrants thereunder and (b) receipt by the Company of the consideration for the 1999 Plan Shares specified in the applicable Board Action and in the 1999 Agent Plan and the warrant certificates evidencing the 1999 Plan Warrants thereunder, the 1999 Plan Shares will be validly issued, fully paid and nonassessable; and

(iv)    following due execution and delivery of the applicable warrant certificates evidencing the 2011 Plan Warrants by or on behalf of the Company, the 2011 Plan Warrants will constitute valid and binding obligations of the Company.

The opinion expressed in paragraph (iv) above with respect to the valid and binding nature of obligations may be limited by bankruptcy, insolvency, reorganization, receivership, moratorium or other laws affecting creditors’ rights (including, without limitation, the effect of statutory and other law regarding fraudulent conveyances, fraudulent transfers and preferential transfers) and by the exercise of judicial discretion and the application of principles of equity, good faith, fair dealing, reasonableness, conscionability and materiality (regardless of whether the 2011 Plan Warrants are considered in a proceeding in equity or at law).

This opinion letter has been prepared for your use in connection with the Registration Statement. We assume no obligation to advise you of any changes in the foregoing subsequent to the effective date of the Registration Statement.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement and to the reference to this firm under the caption “Legal Matters” in the prospectus constituting a part of the Registration Statement. In giving this consent, we do not thereby admit that we are an “expert” within the meaning of the Securities Act of 1933, as amended.

Very truly yours,

/s/ HOGAN LOVELLS US LLP

HOGAN LOVELLS US LLP

3