Exhibit 5.1

799 9th Street NW

Suite 500

Washington, DC 20001-4501

202-585-8000

July 14, 2015

Gannett Co., Inc.

7950 Jones Branch Drive

McLean, Virginia 22107

Ladies and Gentlemen:

We have acted as counsel to Gannett Co., Inc., a Delaware corporation (the “Company”), in connection with a post-effective amendment to a registration statement on Form S-8, Registration No. 333-205321 (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”) relating to a total of up to 11,000,000 shares of the Company’s common stock, par value $.01 per share (the “Common Stock”), issuable under the Gannett Co., Inc. 2015 Omnibus Incentive Compensation Plan (the “Plan”).

In connection with this opinion, we have examined such corporate records and other documents (including the written document constituting the Plan, the Registration Statement and the Company’s amended and restated certificate of incorporation and bylaws), and have made such investigations of law as we have deemed necessary or appropriate as a basis for the opinion expressed below.

As to questions of fact material to this opinion, we have, when relevant facts were not independently established, relied upon certificates of, and information received from, the Company and/or representatives of the Company. We have made no independent investigation of the facts stated in such certificates or as to any information received from the Company and/or representatives of the Company and do not opine as to the accuracy of such factual matters. We also have relied, without investigation, upon certificates and other documents from, and conversations with, public officials.

In rendering this opinion, we have assumed, without investigation, the authenticity of any document or other instrument submitted to us as an original, the conformity to the originals of any document or other instrument submitted to us as a copy, the genuineness of all signatures on such originals or copies, and the legal capacity of natural persons who executed any such document or instrument at the time of execution thereof. We also have assumed that the Registration Statement will remain effective pursuant to the Securities Act at the time of issuance of the Common Stock under the Plan, and the Company will have received the required consideration for the issuance of the Common Stock at or prior to the issuance thereof under the Plan.

Gannett Co., Inc. July 14, 2015 Page 2 NIXON PEABODY LLP ATTORNEYS AT LAW   NIXONPEABODY.COM @NIXONPEABODYLLP

Based upon and subject to the foregoing and the other qualifications and limitations contained herein, we are of the opinion that upon issuance and delivery pursuant to the terms and conditions set forth in the Registration Statement and the Plan, the Common Stock will be validly issued, fully paid and non-assessable.

Members of our firm involved in the preparation of this opinion are licensed to practice law in the State of New York and we do not purport to be experts on, or to express any opinion herein concerning, the laws of any other jurisdiction other than the laws of the State of New York, the federal law of the United States of America and the General Corporation Law of the State of Delaware.

We hereby consent to the filing of a copy of this opinion as Exhibit 5.1 to the Registration Statement. In giving such consent, we do not admit that any member of this firm is an “expert” within the meaning of the Securities Act or the rules and regulations of the Commission thereunder.

This opinion is limited to the matters stated herein, and no opinion or belief is implied or may be inferred beyond the matters expressly stated herein. This opinion is based upon currently existing statutes, rules, regulations and judicial decisions, and we disclaim any obligation to advise you or any other person, or to make any investigations, as to any change in any of these sources of law or subsequent legal or factual developments which might affect any matters or opinions set forth herein.

Very truly yours,

/s/ Nixon Peabody LLP