TERMINATION BENEFITS AGREEMENT

Exhibit 10-15

TERMINATION BENEFITS AGREEMENT

This Termination Benefits Agreement (“Agreement”) is made as of March 16, 2011 between Gannett Co., Inc., a Delaware corporation (“Gannett”), and David Payne (“Payne”).

Gannett desires to appoint Payne as its Senior Vice President and Chief Digital Officer and, to secure his acceptance of this position, desires to memorialize the compensation and benefits he would receive in the event his employment terminates under certain circumstances.

Gannett and Payne hereby agree as follows:

1. Termination of Employment by Payne. Payne shall have the right to terminate his employment with Gannett for “Good Reason” upon 30 days’ written notice to Gannett given within 90 days following the occurrence of any of the following events, each of which shall constitute a “Good Reason” for such termination:

(a) Payne is not elected or retained as Senior Vice President and Chief Digital Officer (or a substantially similar title or such other senior executive position as Payne may agree in writing to serve in);

(b) Gannett acts to materially reduce Payne’s duties, responsibilities, or authority of his position and Gannett does not remedy such situation within 30 days after receipt of written notice from Payne;

(c) Gannett materially breaches this Agreement and Gannett does not remedy such breach within 30 days after receipt of written notice from Payne.

2. Termination of Employment by Gannett. Gannett shall have the right to terminate Payne’s employment for “Good Cause” upon written notice to Payne describing in detail the event that constitutes Good Cause following the occurrence of any of the following events, each of which shall constitute a “Good Cause” for such termination:

(a) intentional misappropriation of Gannett funds or property by Payne;

(b) unreasonable and persistent neglect or refusal by Payne to perform the duties of his position which he does not remedy within 30 days after receipt of written notice from Gannett specifying such alleged neglect or persistent refusal to perform;

(c) material breach by Payne of this Agreement which he does not remedy within 30 days after receipt of written notice from Gannett specifying such alleged material breach; or

(d) conviction of Payne of a felony.

Gannett may also terminate Payne’s employment for convenience (i.e., for any reason other than Good Cause), subject to the applicable provisions of this Agreement that are intended to survive termination of employment.

3. Consequence of Termination of Employment. If Payne terminates his employment with Gannett for any reason other than Good Reason or Gannett terminates his employment for Good Cause, Payne shall have no further rights and Gannett shall have no further obligations under this Agreement except as may be required by applicable labor, employment and wage payment law. If Payne terminates his employment for Good Reason or Gannett terminates Payne’s employment for convenience, then conditioned upon and subject to Payne executing a valid release agreement in such form as Gannett may reasonably require with respect to claims which Payne or his estate or beneficiaries may have arising out of Payne’s employment (the “Release”), the following shall apply:

(a) Payne shall be paid in accordance with normal payroll practices all earned but unpaid compensation, accrued vacation and accrued but unreimbursed expenses required to be reimbursed through the date his employment terminates (the “Termination Date”); and

(b) Gannett shall pay to Payne on the 30^th day after the Termination Date provided that the Release has become effective and non-revocable as of that date, a cash lump sum severance payment equal to the sum of (i) his annual base salary in effect on the Termination Date and (ii) the greater of (A) his most recent annual bonus as of the Termination Date or (B) the average of his three most recent annual bonuses as of the Termination Date.

Notwithstanding the foregoing, Section 3(b) above shall not apply if the Release does not become effective and non-revocable within 30 days after Payne’s Termination Date, and Payne shall have no rights under such section if the Release does not become effective and non-revocable by the 30th day after Payne’s Termination Date. Payne shall not be required to mitigate damages or the amount of any payment provided for under this Agreement by seeking other employment or otherwise, nor will any payments hereunder be subject to offset in respect of any claims which Gannett may have against Payne, nor shall the amount of any payment or benefit provided for in this Section 3 be reduced by any compensation earned as a result of Payne’s employment with another employer. If Payne is entitled to receive a change in control payment under any Gannett transitional compensation or change in control plan then in effect, the amount determined under Section 3(b) shall be offset by the amount paid to Payne under such transitional compensation or change in control plan.

4. Legal Expenses and Interest. If, with respect to any alleged failure by Gannett to comply with any of the terms of this Agreement, Payne institutes or responds to legal action to assert or defend the validity of, enforce his rights under, or recover damages for breach of this Agreement and thereafter Gannett is found in a judgment no longer subject to review or appeal to have breached this Agreement in any material respect, then Gannett shall indemnify Payne for his reasonable attorneys’ fees and costs in connection with such legal action. Gannett shall pay Payne such indemnified expenses by the end the calendar year in which such judgment is reached or, if later, by the 15th day of the third month after the date on which such judgment is reached.

5. Transferability. The rights, benefits and obligations of Gannett under this Agreement shall be transferable, and all covenants and agreements hereunder shall inure to the benefit of and be enforceable by or against, its successors and assigns.

2

Whenever the term “Gannett” is used in this Agreement, such term shall mean and include Gannett Co., Inc. and its successors and assigns. The rights and benefits of Payne under this Agreement shall not be transferable other than rights to property or compensation that may pass on his death to his estate or beneficiaries through his will or the laws of descent and distribution.

6. Severability. If any provision of this Agreement or the application thereof is held invalid or unenforceable, the invalidity or unenforceability thereof shall not affect any other provisions of this Agreement which can be given effect without the invalid or unenforceable provision, and to this end the provisions of this Agreement are to be severable.

7. Amendment; Waiver. This Agreement contains the entire agreement of the parties with respect to the matters contained herein. No amendment or modification of this Agreement shall be valid unless evidenced by a written instrument executed by the parties hereto. No waiver by either party of any breach by the other party of any provision or conditions of this Agreement shall be deemed a waiver of any similar or dissimilar provision or condition at the same or any prior or subsequent time.

8. Tax Withholding. Gannett may withhold from any payments due to Payne hereunder, such amounts as its independent public accountants may determine are required to be withheld under applicable federal, state and local tax laws.

9. Restrictive Covenant.

(a) Payne agrees that (i) during the period of his employment hereunder and (ii) provided that Payne has received the payment under Section 3(b) above, or if Payne is terminated for Good Cause as defined in Section 2, for a period of one (1) year after he ceases employment, he will not, without the written consent of Gannett, seek or obtain a position with a Competitor (as defined below) in which Payne will use or is likely to use any confidential information or trade secrets of Gannett, or in which Payne has duties for such Competitor within the United States that involve Competitive Services (as defined below) and that are the same or similar to those services actually performed by Payne for Gannett.

(b) Payne understands and agrees that the relationship between Gannett and each of its employees constitutes a valuable asset of Gannett and may not be converted to Payne’s own use. Accordingly, Payne hereby agrees that (i) during the period of his employment hereunder and (ii) for a period of six months after he ceases employment, Payne shall not directly or indirectly, on his own behalf or on behalf of another person, solicit or induce any employee to terminate his or her employment relationship with Gannett or any affiliate of Gannett or to enter into employment with another person. The foregoing shall not apply to employees who respond to solicitations of employment directed to the general public or who seek employment at their own initiative.

(c) For the purposes of this Section 9, “Competitive Services” means the provision of goods or services that are competitive with any goods or services offered by Gannett as of the date of this Agreement, including, but not limited to newspapers,

3

non-daily publications, television, radio, cable, digital, Internet, and other news and information services, and “Competitor” means any individual or any entity or enterprise engaged, wholly or in part, in Competitive Services. The parties acknowledge that Gannett may from time to time during the term of this Agreement change or increase the line of goods or services it provides, and Payne agrees to amend this Agreement from time to time to include such different or additional goods and services to the definition of “Competitive Services” for purposes of this Section 9.

(d) Payne agrees that due to his position of trust and confidence the restrictions contained in this Section 9 are reasonable, and the benefits conferred on his in this Agreement, including his compensation, are adequate consideration, and since the nature of Gannett’s business is national in scope, the geographic restriction herein is reasonable.

(e) Payne acknowledges that a breach of this Section 9 will cause irreparable injury and damage, which cannot be reasonably or adequately compensated by money damages. Accordingly, he acknowledges that the remedies of injunction and specific performance shall be available in the event of such a breach, and Gannett shall be entitled to money damages, costs and attorneys’ fees, and other legal or equitable remedies, including an injunction pending trial, without the posting of bond or other security. Any period of restriction set forth in this Section 9 shall be extended for a period of time equal to the duration of any breach or violation thereof.

(f) In the event of Payne’s breach of this Section 9, in addition to the injunctive relief described above, Gannett’s remedy shall include (i) the right to require Payne to account for and pay over to Gannett all compensation, profits, monies, accruals, increments or other benefits derived or received by Payne as the result of any transactions constituting a breach of the restrictive covenants in this Section 9, and (ii) in the case of a breach during the period described in Section 9(a)(ii) or 9(b)(ii) above, the forfeiture and return to Gannett of any payment made under Section 3(b) above.

(g) In the event that any provision of this Section 9 is held to be in any respect an unreasonable restriction, then the court so holding may modify the terms thereof, including the period of time during which it operates or the geographic area to which it applies, or effect any other change to the extent necessary to render this Section 9 enforceable, it being acknowledged by the parties that the representations and covenants set forth herein are of the essence of this Agreement.

10. Confidentiality. Payne agrees to keep confidential the existence of this Agreement and its terms; provided however, that Payne may disclose such terms as are required by law; to his legal, financial and tax advisors and professionals; and to members of his immediate family.

11. Section 409A. The parties intend that benefits under this Agreement are to be either exempt from, or comply with, the requirements of Section 409A of the Code, as amended, and the Treasury Department regulations and other authoritative guidance issued thereunder, and shall be interpreted and administered in accordance with the intent that Payne not be subject to tax under Section 409A of the Code. If any provision

4

of the Agreement would otherwise conflict with or frustrate this intent, that provision will be interpreted and deemed amended so as to avoid the conflict. Any reference in this Agreement to “terminates employment”, “employment terminates”, or similar phrase shall mean an event that constitutes a “separation from service” within the meaning of Section 409A. Notwithstanding anything to the contrary contained herein, in the event that Gannett determines that payments or benefits under this Agreement would otherwise be subject to tax under Section 409A of the Code because Payne is a “specified employee” within the meaning of Section 409A of the Code, such payments or benefits shall not commence until the first day of the seventh month after the Termination Date (or, if earlier, the date Payne dies).

12. Recovery of Compensation in Restatement Situations. Gannett will, to the extent permitted or required by governing law or regulations, as may be amended from time to time, or its recoupment or clawback policy, as may be amended from time to time, require reimbursement of any compensation paid to Payne after the date hereof where (a) Gannett is required to prepare an accounting restatement due to material non-compliance with any financial reporting requirements under the securities laws; (b) the compensation payment was predicated upon the achievement of certain financial results, and (c) a lower payment would have been made to Payne based upon the restated financial results. In each such instance, Gannett will seek to recover Payne’s relevant compensation paid over a period of no less than three years prior to the restatement, regardless of whether Payne is then employed by Gannett.

13. Governing Law. This Agreement shall be governed by and construed under and in accordance with the laws of the State of Delaware without regard to principles of conflicts of laws.

14. Term. This Agreement shall automatically expire and be of no further force or effect on the third anniversary of the date hereof except as otherwise expressly provided herein and with respect to the enforcement of any rights and obligations that accrued on or before the expiration date.

IN WITNESS WHEREOF, the parties have executed this Agreement as of the date first set forth above.

5