Exhibit 4.1

EXECUTION COPY

SECOND AMENDMENT TO STOCKHOLDER PROTECTION AGREEMENT

THIS SECOND AMENDMENT (the “Amendment”), dated as of April 17, 2007, to the Stockholder Protection Agreement (the “Rights Agreement”), dated as of May 8, 1997, as amended by the Amendment to Stockholder Protection Agreement, dated as of March 8, 2007 (the “First Amendment”), between Catalina Marketing Corporation, a Delaware corporation (the “Corporation”), and Mellon Investor Services LLC (f/k/a ChaseMellon Shareholder Services, L.L.C.) (the “Rights Agent”), is being executed at the direction of the Corporation. Capitalized terms used without definition in this Amendment shall have the meanings ascribed to them in the Rights Agreement.

WHEREAS, the Corporation, Checkout Holding Corp., a Delaware corporation (“Parent”), and Checkout Acquisition Corp., a Delaware corporation and a wholly-owned subsidiary of Parent (“Merger Sub”), intend to enter into an Agreement of Merger (the “Merger Agreement”) pursuant to which, among other things, Merger Sub will merge with and into the Corporation (the “Merger”), with the Corporation surviving as a wholly owned subsidiary of Parent;

WHEREAS, on April 17, 2007, the Board of Directors of the Corporation (the “Board”) resolved to amend the Rights Agreement to render the Rights inapplicable to the transactions contemplated by the Merger Agreement;

WHEREAS, the Board, with the advice of its financial advisors, has determined that, based on the capitalization of the Corporation, current events and circumstances relating to the ownership and status of the Corporation and the recent trading prices of the Common Stock, the Exercise Price contained in the Rights Agreement, as adjusted, would not have sufficient dilutive impact to protect the Corporation’s stockholders following the Separation Time;

WHEREAS, in order to ensure that the Corporation’s stockholders are provided protection under the Rights Agreement for an appropriate period of time, the Board has determined that it is in the best interests of the Corporation and its stockholders to amend the Rights Agreement to extend the Expiration Time to the earlier of the effective time of the merger as set forth in the Merger Agreement or April 22, 2008, and to increase the Exercise Price, as adjusted through the date hereof, from $40 to $90; and

WHEREAS, Section 4.4 of the Rights Agreement permits the Corporation from time to time to supplement and amend the Rights Agreement.

NOW, THEREFORE, in consideration of the foregoing and the agreements, provisions and covenants herein contained, the parties agree as follows:

1.	A new Section 4.19 is hereby added to the Rights Agreement as follows:

“4.19. ADDITIONAL PERMITTED TRANSACTIONS. Reference is made to the Agreement of Merger by and among Checkout Holding Corp., a Delaware corporation (“H&F Parent”), Checkout Acquisition Corp., a Delaware corporation and a wholly owned subsidiary of Parent (“H&F Merger Sub”), and the Corporation, dated as of April 17, 2007, as it may be amended from time to time (the “H&F Merger Agreement”). All capitalized terms used in this Section 4.19 shall have the meanings given to them in the H&F Merger

EXECUTION COPY

Agreement unless otherwise defined in this Agreement. Notwithstanding any other provision of this Agreement to the contrary, neither H&F Parent nor H&F Merger Sub nor any of their respective Affiliates or Associates shall be or become an Acquiring Person, and no Separation Time shall occur, and the Rights will not separate from the Common Stock, as a result of the execution, delivery, announcement, consummation or performance of the H&F Merger Agreement or the Voting Agreements, the Merger or any of the other transactions contemplated by the H&F Merger Agreement or the Voting Agreements, in each case, in accordance with the terms thereof, as such terms may be amended from time to time, and none of the Corporation, H&F Parent, H&F Merger Sub, nor the Surviving Corporation, nor any of their respective Affiliates or Associates, shall have any obligations under this Agreement as of and following the execution and delivery of the H&F Merger Agreement, and/or the execution and delivery of the Voting Agreements, and/or the consummation of the Merger, and/or the Effective Time to any holder (or former holder) of Rights; provided, however, that if after the date of execution of the H&F Merger Agreement, the Merger is not consummated in accordance with the terms of the H&F Merger Agreement and the Merger Agreement is terminated in accordance with its terms, this Section 4.19 shall no longer be applicable with respect to the determination of whether H&F Parent or H&F Merger Sub or any of their respective Affiliates or Associates is an “Acquiring Person” at any time thereafter. The Corporation shall promptly provide notice to the Rights Agent of (i) the Effective Time (once it is known to the Corporation) and (ii) any termination of the H&F Merger Agreement in accordance with its terms.”

2. Section 1.1(d) of the Rights Agreement is hereby amended by adding the following sentence to the end of such section:

“For purposes of this Agreement, neither Hellman & Friedman LLC nor any of its Affiliates or Associates will be deemed to be the Beneficial Owner of, to have Beneficial Ownership of, or to Beneficially Own the shares of Common Stock subject to the Voting Agreements as a result of the execution, delivery or performance of the Voting Agreements or the H&F Merger Agreement (all capitalized terms used in this sentence but not otherwise defined shall have the meanings given to them in the H&F Merger Agreement (as such term is defined in Section 4.19 of this Agreement)).”

3. Section 1.1(i) of the Rights Agreement is hereby amended and restated to read in its entirety as follows:

“(i) “Exercise Price” as of April 17, 2007 shall initially be $90, subject to adjustment from time to time thereafter as provided in Section 2.4 hereof.”

4. Section 1.1(j) of the Rights Agreement is hereby amended and restated to read in its entirety as follows:

“(j) “Expiration Time” shall be the earlier of (i) the close of business on April 22, 2008 or (ii) the Effective Time (all capitalized terms used but not defined in this Section 1.1(j) shall have the meanings given to them in the H&F Merger Agreement (as such term is defined in Section 4.19 of this Agreement)). The Corporation shall provide prior written notice of the Expiration Time to the Rights Agent.”

EXECUTION COPY

5. The first sentence of Section 2.4(a) of the Rights Agreement is hereby amended and restated to read in its entirety as follows:

“If the Company shall at any time after April 17, 2007 and prior to the Expiration Time (i) declare or pay a dividend on Common Stock payable in Common Stock (or other capital stock), (ii) subdivide the outstanding Common Stock or (iii) combine the outstanding Common Stock into a smaller number of shares of Common Stock, the Exercise Price and number of Rights outstanding, or, if the payment or effective date therefor shall occur after the Separation Time, the securities purchasable upon exercise of Rights shall be adjusted in the manner set forth below.”

6. The fourth sentence of Section 2.4(a) of the Rights Agreement is hereby amended and restated to read in its entirety as follows:

“If after April 17, 2007 and prior to the Expiration Time the Company shall issue any shares of capital stock other than Common Stock in a transaction of a type described in the first sentence of this Section 2.4(a) or shall issue any Voting Stock in a reclassification of the Common Stock (including any such reclassification in connection with a consolidation or merger in which the Company is the continuing or surviving corporation), shares of such capital stock shall be treated herein as nearly equivalent to shares of Common Stock as may be practicable and appropriate under the circumstances and the Company and the Rights Agent agree to amend this Agreement to effect such treatment.”

7. For the avoidance of doubt, any adjustment made to the number of Rights outstanding prior to the date hereof pursuant to Section 2.4 of the Rights Agreement shall remain unchanged by this Amendment.

8. The last sentence of Section 3.1(a) is hereby amended and restated to read in its entirety as follows:

“In no case shall the Rights Agent be liable for punitive, special, indirect, incidental or consequential loss or damage of any kind whatsoever, even if the Rights Agent has been advised of the likelihood of such loss or damage.”

9. This Amendment shall become effective as of the day and year first written above. Except as modified by this Amendment, the Rights Agreement, as amended, shall remain in full force and effect without any modification. In the event of a conflict or inconsistency between this Amendment and the Rights Agreement, as amended, and the exhibits thereto, the provisions of this Amendment shall govern.

10. By executing this Amendment, the Corporation certifies that this Amendment has been duly executed and delivered and is in compliance with the terms of Section 4.4 of the Rights Agreement. This Amendment shall be irrevocable and each of Parent and Merger Sub shall be an express third party beneficiary hereof.

11. This Amendment may be executed in several counterparts, each of which shall constitute an original and all of which, when taken together, shall constitute one agreement.

EXECUTION COPY

[REMAINDER OF PAGE INTENTIONALLY LEFT BLANK]

The parties hereto have caused this Amendment to be executed and delivered as of the day and year first written above.

CATALINA MARKETING CORPORATION

By:

/s/ L. Dick Buell

Name:

L. Dick Buell

Title:

Chief Executive Officer

MELLON INVESTOR SERVICES LLC

By:

/s/ Judy Hsu

Name:

Judy Hsu

Title:

Client Relationship Executive

[SIGNATURE PAGE TO SECOND AMENDMENT TO STOCKHOLDER PROTECTION AGREEMENT]