EXHIBIT 5.1

July 2, 2010

Frontier Communications Corporation

7.875% Senior Notes Due 2015

8.250% Senior Notes Due 2017

8.500% Senior Notes Due 2020

8.750% Senior Notes Due 2022

Form S-4 Registration Statement

Ladies and Gentlemen:

We have acted as counsel for Frontier Communications Corporation, a Delaware corporation (the “Company”), in connection with the filing by the Company with the Securities and Exchange Commission (the “Commission”) of a registration statement on Form S-4 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Act”), relating to the issuance and exchange of up to $500,000,000 aggregate principal amount of new 7.875% Senior Notes due 2015 (the “2015 Exchange Notes”) for a like aggregate principal amount of outstanding 7.875% Senior Notes due 2015 (the “Original 2015 Notes”), up to $1,100,000,000 aggregate principal amount of new 8.250% Senior Notes due 2017 (the “2017 Exchange Notes”) for a like aggregate principal amount of outstanding 8.250% Senior Notes due 2017 (the “Original 2017 Notes”), up to $1,100,000,000 aggregate principal amount of new 8.500% Senior Notes due 2020 (the “2020 Exchange Notes”) for a like aggregate principal amount of outstanding 8.500% Senior Notes due 2020 (the “Original 2020 Notes”) and up to $500,000,000 aggregate principal amount of new 8.750% Senior Notes due 2022 (the “2022 Exchange Notes” and, collectively with the 2015 Exchange Notes, the 2017 Exchange Notes and the 2020 Exchange Notes, the “Exchange Notes”) for a like aggregate principal amount of outstanding 8.750% Senior Notes due 2022 (the “Original 2022 Notes” and, collectively with the Original 2015 Notes, the Original 2017 Notes and the Original 2020 Notes, the “Original Notes”). The Original Notes have certain transfer restrictions. The Exchange Notes are to be issued pursuant to the indenture (the “Original Indenture”) dated as of April 12, 2010, between New Communications Holdings Inc. (“Spinco”) and The Bank of New York Mellon, as trustee, as supplemented and amended by the First Supplemental Indenture (together with the Original Indenture, the “Indenture”) dated as of July 1, 2010, between the Company (as successor obligor to Spinco) and The Bank of New York Mellon, as trustee.

In that connection, we have examined originals, or copies certified or otherwise identified to our satisfaction, of such documents, corporate records and other instruments as we have deemed necessary or appropriate for the purposes of this opinion, including (a) the Indenture and the form of Exchange Note included therein, (b) the Certificate of Incorporation of the Company, as amended, (c) the By-Laws of the Company, and (d) resolutions adopted by the Board of Directors of the Company on March 25, 2010.

Based on the foregoing and subject to the qualifications set forth herein, we are of opinion as follows:

1. The Exchange Notes have been duly authorized and, when executed and authenticated in accordance with the provisions of the Indenture and issued and delivered in exchange for the Original Notes, will constitute legal, valid and binding obligations of the Company, entitled to the benefits of the Indenture and enforceable against the Company in accordance with their terms (subject to applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent transfer and other similar laws affecting creditors’ rights generally from time to time in effect and to general principles of equity, including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing, regardless of whether considered in a proceeding in equity or at law). In expressing the opinion set forth in this paragraph 1, we have assumed, with your consent, that the form of the Exchange Notes will conform to that included in the Indenture.

2. The Indenture has been duly authorized, executed and delivered by the Company and constitutes a legal, valid and binding obligation of the Company enforceable against the Company in accordance with its terms (subject to applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent transfer and other similar laws affecting creditors’ rights generally from time to time in effect and to general principles of equity, including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing, regardless of whether considered in a proceeding in equity or at law).

We are admitted to practice in the State of New York and we express no opinion as to matters governed by any laws other than the laws of the State of New York, the General Corporation Law of the State of Delaware and the Federal laws of the United States of America.

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. We also consent to the reference to our firm under the caption “Legal Matters” in the prospectus constituting a part of the Registration Statement. In giving such consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission.

We are furnishing this opinion to you, solely for your benefit. This opinion may not be relied upon by any other person or for any other purpose or used, circulated, quoted or otherwise referred to for any other purpose.

Very truly yours,

/s/ Cravath, Swaine & Moore LLP

Frontier Communications Corporation

3 High Ridge Park

Stamford, Connecticut 06905

O

2