QuickLinks -- Click here to rapidly navigate through this document

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"), 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.

        The Prospectus provides that it will be supplemented in the future by one or more supplements to the Prospectus (each, a "Prospectus Supplement"). The Registration Statement and the Prospectus (as supplemented by the applicable Prospectus Supplement(s)) relate to the issuance and sale from time to time by the Company of securities with an aggregate public offering price of up to $150,000,000 consisting of: (i) shares of the Company's common stock, par value $.01 per share (the "Common Stock"); (ii) one or more series of preferred stock, par value $.01 per share (the "Preferred Stock"); (iii) one or more series of debt securities which may be either senior or subordinated debt securities (the "Debt Securities"); (iv) warrants to purchase shares of Common Stock (the "Common Stock Warrants"); and (v) warrants to purchase shares of Preferred Stock (the "Preferred Stock Warrants" and, together with the Common Stock Warrants, the "Warrants"), plus any additional Common Stock, Preferred Stock, Debt Securities or Warrants that may be registered pursuant to any subsequent registration statements that the Company may hereafter file with the Commission pursuant to Rule 462(b) under the Securities Act (collectively, the "Securities"). Any shares of Preferred Stock may be convertible into or exchangeable for shares of Common Stock, shares of another series of Preferred Stock or other securities. Any Debt Securities may also be convertible into or exchangeable for shares of Common Stock or other securities.

        The Debt Securities may be issued pursuant to (i) a senior indenture (the "Senior Indenture") in the case of senior Debt Securities or (ii) a subordinated indenture (the "Subordinated Indenture") in the case of subordinated Debt Securities, each of which will be between the Company and a financial institution to be identified therein as trustee (the "Trustee"), in the forms included as Exhibits 4.3 and 4.4 to the Registration Statement, respectively, as each such indenture may be supplemented from time to time. The Senior Indenture and the Subordinated Indenture are referred to herein collectively as, the "Indentures." The Warrants may be issued pursuant to a warrant agreement between the Company and a financial institution to be identified therein as the warrant agent (the "Warrant Agent"), as such warrant agreement may be supplemented from time to time (the "Warrant Agreement").

        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 opinions 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 none of the terms of any of the Securities to be established after the date hereof, nor the issuance and delivery of such Securities, nor the compliance by the Company with the terms of such Securities will violate any applicable law or will result in a violation of any provision of any instrument or agreement then binding upon the Company, or any restriction imposed by any court or governmental body having jurisdiction over the Company.

        Based upon and subject to the foregoing, we are of the following opinion:

1.

With respect to any shares of Common Stock to be offered pursuant to the Registration Statement, when the Registration Statement and any required post-effective amendment(s) thereto has become effective under the Securities Act (and assuming that such effectiveness shall not have been terminated or rescinded) and any Prospectus Supplement(s) required by applicable laws has been delivered and filed as required by such laws, and upon adoption by the Board of Directors of the Company of a resolution in form and content as required by applicable law authorizing the issuance of such shares of Common Stock and upon issuance and delivery of and payment of legal consideration not less than the par value thereof for such shares of Common Stock in the manner contemplated in the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and by such resolution, and assuming that (a) the terms of such shares of Common Stock as issued, delivered and sold are as described in the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and such resolution, and (b) at the time of issuance of such shares of Common Stock, the Company has a sufficient number of authorized but unissued shares of Common Stock under the Eighth Amended and Restated Certificate of Incorporation of the Company filed with the Secretary of State of the State of Delaware on February 8, 2005, as amended from time to time (the "Certificate of Incorporation"), such shares of Common Stock (including any shares of Common Stock duly issued (i) upon the conversion or exchange of any shares of Preferred Stock that are convertible into or exchangeable for Common Stock, (ii) upon the conversion or exchange of any Debt Securities that are convertible into or exchangeable for Common Stock or (iii) upon the exercise of Warrants that are exercisable for Common Stock) will be validly issued, fully paid and nonassessable.



2.

With respect to any shares of Preferred Stock to be offered pursuant to the Registration Statement, when (a) the Registration Statement and any required post-effective amendment(s) thereto has become effective under the Securities Act (and assuming that such effectiveness shall not have been terminated or rescinded) and any Prospectus Supplement(s) required by applicable laws has been delivered and filed as required by such laws, (b) a series of Preferred Stock has been duly established in accordance with the terms of the Certificate of Incorporation and applicable law, and upon adoption by the Board of Directors of the Company of a resolution in form and content as required by applicable law authorizing the issuance of such shares of Preferred Stock and upon issuance and delivery of and payment of legal consideration not less than the par value thereof for such shares of Preferred Stock in the manner contemplated by the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and by such resolution, and (c) the relative rights, preferences and limitations of such series of Preferred Stock have been designated by the Board of Directors of the Company and set forth in a Certificate of Designation properly filed with the Secretary of State of the State of Delaware, and assuming that (i) the terms of such shares of Preferred Stock as issued, delivered and sold are as described in the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and such resolution, and (ii) at the time of issuance of such shares of Preferred Stock, the Company has a sufficient number of authorized but unissued shares of Preferred Stock under the Certificate of Incorporation, such

2

shares of Preferred Stock (including any Preferred Stock duly issued (A) upon the conversion or exchange of any shares of Preferred Stock that are convertible into or exchangeable for another series of Preferred Stock, (B) upon the conversion or exchange of any Debt Securities that are convertible into or exchangeable for Preferred Stock or (C) upon the exercise of Warrants that are exercisable for Preferred Stock) will be validly issued, fully paid and nonassessable.

3.

With respect to any Debt Securities to be offered pursuant to the Registration Statement, when (a) the applicable Indenture has been duly authorized, executed and delivered by the Company and the Trustee, (b) the Debt Securities have been duly authorized and duly established in accordance with the applicable Indenture and applicable law (including, without limitation, by the adoption by the Board of Directors of the Company of a resolution duly authorizing the issuance and delivery of the Debt Securities (the "Debt Securities Authorization")), duly authenticated by the Trustee and duly executed and delivered on behalf of the Company against payment therefor in accordance with the terms and provisions of the applicable Indenture and as contemplated by the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and the Debt Securities Authorization, and (c) the Registration Statement and any required post-effective amendment(s) thereto has become effective under the Securities Act (and assuming that such effectiveness shall not have been terminated or rescinded) and any Prospectus Supplement(s) required by applicable laws has been delivered and filed as required by such laws, and assuming that the terms of the Debt Securities as executed, delivered and sold are as described in the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and the Debt Securities Authorization, such Debt Securities will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.



4.

With respect to any Warrants to be offered pursuant to the Registration Statement, when (a) the Warrant Agreement has been duly authorized, executed and delivered by the Company and the Warrant Agent, (b) the Warrants have been duly authorized and duly established in accordance with the Warrant Agreement and applicable law (including, without limitation, by the adoption by the Board of Directors of the Company of a resolution duly authorizing the issuance and delivery of the Warrants (the "Warrants Authorization")), duly authenticated by the Warrant Agent and duly executed and delivered on behalf of the Company against payment therefor in accordance with the terms and provisions of the Warrant Agreement and as contemplated by the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and the Warrants Authorization, and (c) the Registration Statement and any required post-effective amendment(s) thereto has become effective under the Securities Act (and assuming that such effectiveness shall not have been terminated or rescinded) and any Prospectus Supplement(s) required by applicable laws has been delivered and filed as required by such laws, and assuming that the terms of the Warrants as executed, delivered and sold are as described in the Registration Statement, the Prospectus and the related Prospectus Supplement(s) and the Warrants Authorization, such Warrants will constitute valid and binding obligations of the Company, enforceable against the Company in accordance with their terms.

        The opinions in paragraphs 3 and 4 with respect to the enforceability of the Debt Securities and the Warrants are limited by the effect of: (i) any applicable bankruptcy, insolvency, reorganization, moratorium or similar law and principles affecting creditors' rights generally, including without limitation, fraudulent transfer or fraudulent conveyance laws; (b) public policy considerations or court decisions which may limit rights to obtain indemnification or contribution; and (c) general principles of equity (including, without limitation, concepts of materiality, reasonableness, good faith and fair dealing) and the availability of equitable remedies (including, without limitation, specific performance and equitable relief), regardless of whether considered in a proceeding in equity or at law.

3

        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

4

QuickLinks

Exhibit 5.1