Exhibit 5

[PAUL, HASTINGS, JANOFSKY & WALKER LLP]

November 30, 2004 16264.42618

Catalina Marketing Corporation
200 Carillon Parkway
St. Petersburg, Florida 33716

Re:	Catalina Marketing Corporation
	2004 Employee Payroll Deduction Stock Purchase Plan
	Registration Statement on Form S-8

Ladies and Gentlemen:

     As counsel for Catalina Marketing Corporation, a Delaware corporation (the “Company”), you have requested our opinion in connection with the preparation and filing with the Securities and Exchange Commission of a Registration Statement on Form S-8 (the “Registration Statement”), registering 1,300,000 shares of the Company’s common stock, $0.01 par value per share (the “Common Shares”) for issuance pursuant to the Company’s 2004 Employee Payroll Deduction Stock Purchase Plan.

     We have examined such records and documents and made such examination of law as we have deemed relevant in connection with this opinion. Based on the foregoing, we are of the opinion that the 1,300,000 Common Shares covered by said Registration Statement have been duly and validly authorized and, when issued and paid for in accordance with the terms of the Company’s 2004 Employee Payroll Deduction Stock Purchase Plan, will be legally issued, fully-paid and nonassessable.

     We hereby consent to the filing of this opinion as an exhibit to the above-referenced Registration Statement on Form S-8 of Catalina Marketing Corporation.

Very truly yours,

Paul, Hastings, Janofsky & Walker LLP