Exhibit 5.1

August 22, 2005

FairPoint Communications, Inc.
521 East Morehead Street, Suite 250
Charlotte, North Carolina 28202

Re:    FairPoint Communications, Inc.
Registration Statement on Form S-3

Ladies and Gentleman:

        We have acted as counsel to FairPoint Communications, Inc., a Delaware corporation (the "Company"), in connection with the preparation of the Registration Statement on Form S-3 which was filed with the Securities and Exchange Commission (the "Commission") on August 22, 2005 pursuant to the Securities Act of 1933, as amended (the "Securities Act"), relating to the proposed offer and sale by the selling stockholders identified as such in the Registration Statement of an aggregate of up to 7,599,430 shares of the Company's common stock, par value $0.01 per share (the "Shares"), which Registration Statement includes the prospectus (the "Prospectus"). This opinion is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

        In connection with this opinion, we have examined originals or copies of such documents, resolutions, certificates and instruments of the Company as we have deemed necessary to form a basis for the opinions hereafter expressed. In addition, we have reviewed certificates of public officials, statutes, records and such other instruments and documents and have made such investigations of law as we have deemed necessary to form a basis for the opinion hereinafter expressed. In our examination of the foregoing, we have assumed, without independent investigation: (i) the genuineness of all signatures and the authority of all persons or entities signing all documents examined by us, (ii) the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as certified, conformed or photostatic copies and (iii) the authenticity of the originals of such latter documents. With regard to certain factual matters, we have relied, without independent investigation or verification, upon, and assumed the accuracy and completeness of, statements and representations of representatives of the Company. We have also assumed that the Shares will be sold as described in the Registration Statement.

        Based upon and subject to the foregoing, we are of the opinion that the Shares have been duly authorized and are validly issued, fully paid and nonassessable.

        We are members of the Bar of the State of New York and, accordingly, do not purport to be experts on or to be qualified to express any opinion herein concerning the laws of any jurisdiction other than laws of the State of New York and the Delaware General Corporation Law, including the applicable provisions of the Delaware Constitution and the reported cases interpreting those laws, as currently in effect.

        This opinion letter deals only with the specified legal issues expressly addressed herein, and you should not infer any opinion that is not explicitly addressed herein from any matter stated in this letter.

        We consent to the use of this opinion as an exhibit to the Registration Statement and to the reference to our firm under the caption "Legal Matters" in the Prospectus. In giving such consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act and the rules and regulations thereunder. This opinion is rendered to you as of the date hereof and we assume no obligation to advise you or any other person hereafter with regard to any change after the date hereof in the circumstances or the law that may bear on the matters set forth herein even though the changes may affect the legal analysis or legal conclusion or other matters in this letter.

Very truly yours,

/s/ Paul, Hastings, Janofsky & Walker LLP