CHANGE OF CONTROL AGREEMENT

EXHIBIT 10.21

CHANGE OF CONTROL AGREEMENT

This Agreement between L. Xxxx Xxxxx (“you”) and Catalina Marketing Corporation (the “Company”), made on October 1, 2006, promises you severance benefits if, following a Change in Control, you are terminated without Cause or resign for Good Reason as set forth in this Agreement. Capitalized terms are defined in the last section of this Agreement.

1. Purpose

The Company considers a sound and vital management team to be essential. Management personnel who become concerned about the possibility that the Company may undergo a Change in Control may resign or become distracted. Accordingly, the Board has determined that appropriate steps should be taken to minimize the distraction you may suffer from the possibility of a Change in Control. One step is to enter into this Agreement with you.

2. Your Agreement

If one or more Potential Changes in Control occur during the Term of this Agreement, you agree not to resign for at least six full calendar months after a Potential Change in Control occurs, except as follows: (a) you may resign if you are given Good Reason to do so; and (b) you may resign because of retirement when or after you achieve age 65 or because you become unable to work due to Disability.

3. Events That Trigger Severance Benefits

(a) Termination After a Change in Control

You will receive Severance Benefits under this Agreement if, within two years after a Change in Control has occurred (so long as the Change in Control occurs during the Term of this Agreement), the Company terminates your employment without Cause or you resign for Good Reason.

(b) Termination After a Potential Change in Control

You also will receive Severance Benefits under this Agreement if, during the Term of this Agreement and after a Potential Change in Control has occurred but before a Change in Control actually occurs, the Company terminates your employment without Cause or you resign for Good Reason.

(c) Successor Fails to Assume This Agreement

You also will receive Severance Benefits under this Agreement if, during the Term of this Agreement, a successor to the Company does not assume this Agreement, as provided in Section 12(a).

4. Events That Do Not Trigger Severance Benefits

You will not be entitled to Severance Benefits if your employment ends because the Company terminates you for Cause or on account of Disability or because you resign without Good Reason, retire or die. Except as provided in Section 3(c), you are not entitled to Severance Benefits while you remain protected by this Agreement and remain employed by the Company, its affiliates or their successors.

5. Termination Procedures

If the Company terminates you within two years after a Change in Control occurring during the Term of this Agreement, the Company will provide you with 30 days’ advance written notice of your termination. Advance notice is not required if the Company terminates you for Cause. In any case, the notice will indicate why you are being terminated and will explain in reasonable detail the facts and circumstances surrounding your termination. If the Company terminates you for Cause, your notice of termination will include a copy of a resolution duly adopted by the affirmative vote of at least a majority of the entire membership of the Board (at a meeting of the Board called and held for the purpose of considering your termination (after reasonable notice to you and an opportunity for you and your counsel to be heard before the Board)). This resolution will state that, in the good faith opinion of the Board, Cause for your termination exists and specify the basis for that opinion in detail. If the Company terminates you without the notice required by this Section, your termination will not be effective.

6. Severance Benefits

(a) In General

If you become entitled to Severance Benefits under this Agreement, you will receive all of the Severance Benefits described in this Section as well as any unpaid base salary, expense reimbursements and vacation days earned before your termination date and any earned but unpaid bonus for the fiscal year before the year of termination. Any unpaid vested amounts or benefits under the Company’s compensation incentive and benefits plans will be paid in accordance with the terms of those plans.

(b) Lump-Sum Payment in Lieu of Future Compensation

In lieu of any further cash compensation for periods after your employment ends and in lieu of any other severance or other similar compensation the Company’s policies entitle you to, you will be paid a cash lump sum equal to 2.99 times your Annual Compensation in effect when your employment ends or, if higher, the highest Annual Compensation in effect immediately before the Change in Control, Potential Change in Control, or Good Reason event for which you terminate employment.

(c) Incentive Compensation

The Company will pay you a cash lump sum equal to the sum of any unpaid incentive compensation (that is not otherwise paid to you) that you are due under any bonus or commission plan for measuring periods completed before you became entitled to Severance Benefits under this Agreement.

- 2 -

(d) Deferred Compensation; Stock Benefits

The Severance Benefits and other terms set forth on this Agreement will not affect your rights under any deferred compensation, savings, retirement, “401(k),” stock purchase, stock grants, stock option or other employee benefit or compensation plan, all of which will be governed by the their own terms. You are reminded that the Company’s stock option plans contain provisions which are effective in connection with a Change in Control.

(e) Group Insurance Benefit Continuation

During the period that begins when you become entitled to Severance Benefits under this Agreement and ends on the last day of the 30^th calendar month afterwards, the Company will provide the life, disability, accident and health insurance benefits (or substantially similar benefits) it was providing to you and your spouse and dependents immediately before you became entitled to Severance Benefits under this Agreement (or immediately before a benefit reduction that constitutes Good Reason, if you terminate employment for that Good Reason). These benefits, which will be at active employee contribution rates, will be treated as satisfying the Company’s COBRA obligations. After benefit continuation under this subsection ends, you and your spouse and dependents will be entitled to any remaining COBRA rights.

(f) Senior Executive Level Career Transition Assistance

The Company will pay for twelve months senior executive level career transition assistance, beginning on any date that you select within 3 months following the effective date of your termination, by an outplacement firm selected by you and acceptable to the Company. If you accept a new position, the Company’s obligation to make continuing payments under this provision ends.

7. Time for Payment

Except as described in Section 20, you will be paid your cash Severance Benefits within five days after you become entitled to Severance Benefits under this Agreement (e.g., within five days following your termination of employment). If the amount you are due cannot be finally determined within that period, you will receive the minimum amount to which you are clearly entitled, as estimated in good faith by the Company. The Company will pay the balance you are due (together with interest at the rate provided in Code Section 1274(b)(2)(B)) as soon as the amount can be determined. The Company will not pay this amount later than 30 days after you terminate employment. If your estimated payment exceeds the amount you are due, the excess will be a loan to you, which you must repay to the Company within five business days after you receive demand by the Company (together with interest at the rate provided in Code Section 1274(b)(2)(B)).

8. Payment Explanation

When payments are made to you, the Company will provide you with a written statement explaining how your payments were calculated and the basis for the calculations. This statement will include any opinions or other advice the Company has received from auditors or consultants as to the calculation of your benefits.

- 3 -

9. Relation to Other Severance Programs

Your Severance Benefits under this Agreement are in lieu of any severance or similar benefits that are payable to you under any other employment agreement or other arrangement with the Company, or in accordance with the Company’s published or unpublished policies. If these other benefits are paid to you, those amounts will be applied to reduce the amount due under this Agreement. This Agreement is the entire agreement between you and the Company and its affiliates with respect to the benefits.

10. Golden Parachute

Your total payments and benefits under this Agreement may exceed the relevant limitations under the “golden parachute” provisions of Code Section 280G. However, nothing in this Agreement will cause the Company to be required to pay to you any amount in excess of the Severance Benefits provided for in this Agreement.

11. Effect of Reemployment

Except as described in the provisions of paragraph 9 of this Agreement, your Severance Benefits under this Agreement won’t be reduced by any other compensation you earn or could have earned from another source.

12. Successors

(a) Assumption Required

In addition to obligations imposed by law on a successor to the Company, during the Term of this Agreement the Company will require any successor to the Company, including any Change in Control (whether by sale of assets or securities, or merger transaction, or otherwise) in writing to take on and agree to perform this Agreement just as the Company was required to perform. If the Company fails to obtain the assumption and agreement before the effective date of a succession, you will be entitled to Severance Benefits as if you were terminated by the Company without Cause on the effective date of that succession.

(b) Heirs and Assigns

This Agreement will serve to the benefit of, and be enforceable by, your personal or legal representatives, executors, administrators, successors, heirs, distributees, devisees and legatees. If you die while any amount is still payable to you under this Agreement, that amount will be paid to the executor, personal representative or administrator of your estate.

13. Amendments

This Agreement may be modified only by a written agreement signed by you and an authorized officer of the Company.

- 4 -

14. Governing Law

This Agreement creates a “top hat” employee benefit plan subject to the Employee Retirement Income Security Act of 1974, and it will be interpreted, administered, and enforced in accordance with that law; the Company is the “plan administrator.” To the extent that state law is applicable, the statutes and common law of the State of Florida (excluding its choice of laws provisions) will apply.

15. Claims

(a) When Required; Attorneys’ Fees

You do not need to present a formal claim to receive benefits payable under this Agreement. However, if you believe that your rights under this Agreement are being violated, you must file a formal claim with the Company in accordance with the procedures set forth in this Section. If the claim cannot be resolved under these administrative procedures, the Company will pay your reasonable attorneys’ fees and related costs in enforcing your rights under this Agreement if you ultimately prevail.

(b) Initial Claim

Your claim must be presented to the Company in writing. Within 70 days after receiving the claim, a claims official appointed by the Company will consider your claim and issue his or her determination thereon in writing. The claims official may extend the determination period for up to an additional 90 days by giving you written notice. With your consent, the initial claim determination period can be extended further. If you can establish that the claims official failed to respond to your claim in a timely manner, you may treat the claim as having been denied by the claims official.

(c) Claim Decision

If your claim is granted, the benefits or relief you are seeking will be provided. If your claim is wholly or partially denied, the claims official will, within 70 days (or a longer period, as described above), provide you with written notice of the denial, setting forth, in a manner calculated to be understood by you: (i) the specific reason or reasons for the denial; (ii) specific references to the provisions on which the denial is based; (iii) a description of any additional material or information necessary for you to perfect your claim, together with an explanation of why the material or information is necessary; and (iv) an explanation of the procedures for appealing denied claims. If you establish that the claims official has failed to respond to your claim in a timely manner, you may treat the claim as having been denied by the claims official.

(d) Appeal of Denied Claims

You may appeal the claims official’s denial of your claim in writing to an appeals official designated by the Company (which may be a person, committee, or other entity) for a full and fair appeal. You must appeal a denied claim within 60 days after your receipt of written notice denying your claim, or within 60 days after the written notice was due, if the written

- 5 -

notice was not sent. In connection with the appeals proceeding, you (or your duly authorized representative) may review pertinent documents and may submit issues and comments in writing. You may only present evidence and theories during the appeal that you presented during the initial claims stage, except for information the claims official requested you to provide to perfect the claim. You will irrevocably waive any theories you do not in good faith pursue through the appeal stage, such as by failing to file a timely appeal request.

(e) Appeal Decision

The decision by the appeals official will be made within 60 days after your appeal request, unless special circumstances require an extension of time, in which case the decision will be rendered as soon as possible, but not later than 120 days after your appeal request, unless you agree to a greater extension of that deadline. The appeal decision will be in writing, set forth in a manner calculated to be understood by you; it will include specific reasons for the decision, as well as specific references to the pertinent provisions of this Agreement on which the decision is based. If you do not receive the appeal decision by the date it is due, you may consider your appeal to have been denied.

(f) Procedures

The Company will adopt procedures by which initial claims and appeals will be considered and resolved; different procedures may be established for different types of claims. All procedures will be designed to afford you full and fair consideration of your claim. You may not challenge a decision of the Company hereunder in court or in any other administrative proceeding unless and until the claim and appeal procedures described in this Section 15 have been complied with and exhausted.

16. Validity

The invalidity or unenforceability of any part of this Agreement does not affect the validity or enforceability of any other part of this Agreement.

17. Counterparts

This Agreement may be executed in several counterparts, each of which will be deemed an original, but all of which will constitute one and the same instrument.

18. Giving Notice

(a) To the Company

All communications from you to the Company relating to this Agreement must be sent to the Company to its principal business office in St. Petersburg, Florida, in writing, by registered or certified mail, or delivered personally, or as the Company may otherwise notify you in writing.

- 6 -

(b) To You

All communications from the Company to you relating to this Agreement must be sent to you in writing, by registered or certified mail, or delivered personally, addressed as indicated at the end of this Agreement, or as you may otherwise notify the Company in writing.

19. Definitions

(a) Agreement

“Agreement” means this contract, as amended.

(b) Annual Compensation

“Annual Compensation” means your base salary plus which ever is greater: (i) the average bonus and commissions paid to you in the three fiscal years before the year in which the Change in Control took place (or, if less than three, in the number of years you were employed by the Company prior to the year the Change in Control took place); or (ii) the bonus and commissions paid to you in the fiscal year during which the Change in Control took place (including pursuant to Section 6(c)) or, if greater, any later year.

(c) Beneficial Owner

“Beneficial Owner” has the meaning set forth in Rule 13d-3 under the Exchange Act.

(d) Board

“Board” means the Board of Directors of the Company.

(e) Cause

“Cause” has the same meaning as in Section 3(b) of the Severance Agreement.

(f) Change in Control

“Change in Control” means the occurrence of any of the following: (i) the acquisition, directly or indirectly, by any individual or entity or group (as such term is used in Section 13(d)(3) of the Exchange Act) of Beneficial Ownership (except that an individual or entity will be deemed to be the Beneficial Owner of all shares that the individual or entity has the right to acquire without the happening or failure to happen of a material condition or contingency, other than the passage of time) of more than 50% of the total outstanding voting power of capital stock of the Company in respect of the general power to elect directors; (ii) during any two consecutive years, individuals who at the beginning of the period constituted the Board (together with individuals elected to the Board with the approval of at least 66 2/3% of the directors of the Company then still in office who were either directors at the beginning of the period, or whose election or nomination for election was previously so approved) cease for any reason to constitute a majority of the Board then in office; and (iii) (A) the Company consolidates with or merges into another entity or sells all or substantially all of its assets to any individual or entity, or (B) any corporation consolidates with or merges into the Company, which in either event (A) or (B) is pursuant to a transaction in which the

- 7 -

holders of the Company’s voting capital stock in respect of the general power to elect directors immediately prior to the transaction do not own, immediately following such transaction, at least a majority of the voting capital stock in respect of the general power to elect directors of the surviving corporation or the person or entity which owns the assets so sold.

(g) Code

“Code” means the Internal Revenue Code of 1986, as amended.

(h) Company

“Company” means Catalina Marketing Corporation and any successor to its business or assets that (by operation of law, or otherwise) assumes and agrees to perform this Agreement. However, for purposes of determining whether a Change in Control has occurred in connection with such a succession, the successor will not be considered to be the Company.

(i) Disability

“Disability” has the same meaning as in Section 3(c) of the Severance Agreement.

(j) Exchange Act

“Exchange Act” means the Securities Exchange Act of 1934, as amended.

(k) Good Reason

“Good Reason” means the occurrence of any of the following without your express written consent:

(1) A change in your status, title, position or responsibilities (including reporting responsibilities) that is a large reduction of the status, title, position or responsibilities before the change; the assignment to you of many duties or responsibilities that are inconsistent with such status, title, position or responsibilities; or your removal from or failure to reappoint or reelect you to any of such positions, except in connection with the termination of your employment for Cause, for Disability or as a result of your death, or by you other than for Good Reason;

(2) The Company reducing your annual base salary;

(3) The Company requiring you to be based at any place outside a 35-mile radius of your place of employment immediately before a Change in Control, except for reasonably required travel on the Company’s business that isn’t materially greater than those travel requirements before the Change in Control; or

(4) The Company’s failure to (i) continue in effect any material compensation or benefit plan (or a reasonable replacement therefore) in which you were participating immediately before a Change in Control or (ii) provide you with compensation and benefits at least equal (in terms of benefit levels and/or reward opportunities) to those provided for under each employee benefit plan, program and practice as in effect immediately before a Change in Control (or in effect after the Change in Control, if greater).

- 8 -

However, an event that is or would be Good Reason ceases to be Good Reason if: (a) you do not resign within 45 days after the event or you first learn of the event; or (b) the Company reverses the action or cures the default that constitutes Good Reason before you terminate employment; or (c) you were a primary instigator of the Good Reason event and the circumstances make it inappropriate for you to receive benefits under this Agreement (e.g., you agree temporarily to relinquish your position on the occurrence of a merger transaction you negotiate). If you have Good Reason to resign, you may do so even if you are on a leave of absence due to physical or mental illness or any other reason.

(l) Person

“Person” has the meaning given in Section 3(a)(9) of the Exchange Act, as modified and used in Section 13(d) of that Act, and includes a “group,” as defined in Rule 13d-5 promulgated thereunder. However, a Person does not include: (i) the Company or any of its subsidiaries; (ii) a trustee or other fiduciary holding securities under an employee benefit plan of the Company or any of its subsidiaries; (iii) an underwriter temporarily holding securities pursuant to an offering of such securities; or (iv) a corporation owned, directly or indirectly, by the stockholders of the Company in substantially the same proportions as their ownership of stock of the Company.

(m) Potential Change in Control

“Potential Change in Control” means that any of the following has occurred during the term of this Agreement and no event terminating the following has occurred:

(1) Agreement Signed. The Company enters into an agreement that will result in a Change in Control.

(2) Notice of Intent to Seek Change in Control. The Company or any Person publicly announces an intention to take or to consider taking actions that will result in a Change in Control.

(3) Board Declaration. With respect to this Agreement, the Board adopts a resolution declaring that a Potential Change in Control has occurred.

(n) Severance Agreement

“Severance Agreement” means the Severance Agreement dated October 1, 2006, between you and the Company.

(o) Severance Benefits

“Severance Benefits” means your benefits under Section 6 of this Agreement.

- 9 -

(p) Term of this Agreement

“Term of this Agreement” means the period that commences on the date of this Agreement and ends on October 1, 2011.

20. Tax Liabilities and Code Section 409A.

You are solely responsible for the payment of any tax liability (including any taxes and penalties that may arise under Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”)) that may result from any payments or benefits that you receive pursuant to this Agreement. In addition, any such payments or benefits may be reduced by any applicable employment or withholding taxes. In addition, the Company will suspend paying you any cash amounts that you are entitled to receive pursuant to Section 6 during the six-month period following termination of your employment (the “409A Suspension Period”), unless the Company reasonably determines that paying such amounts in accordance with Section 3 won’t result in your liability for additional tax under Section 409A of the Code (“Section 409A”). As soon as reasonably practical after the end of the 409A Suspension Period, you will receive a lump sum payment in cash for an amount equal to any cash payments that the Company does not make during the 409A Suspension Period due to the provisions of Section 409A.

[Remainder of page intentionally left blank

Next page is signature page]

- 10 -

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

CATALINA MARKETING CORPORATION

Date: October 1, 0000

XXXXXXXXX X. XXXXXXXX

Chairman of the Board

Date: October 1, 2006

L. XXXX XXXXX

Company notices to you will be addressed as follows (or in any other manner you notify the Company to use):

L. Xxxx Xxxxx

0000 Xxxxxxxx Xxxx. #0

Xxxxx, XX 00000

- 11 -