Exhibit 23.1

Consent of Independent Registered Certified Public Accounting Firm

We hereby consent to the incorporation by reference in this Registration Statement on Form S-8 of our report dated July 14, 2004 relating to the financial statements of Catalina Marketing Corporation, which appears in Catalina Marketing Corporation’s Annual Report on Form 10-K for the year ended March 31, 2004.

/s/ PricewaterhouseCoopers LLP

Tampa, Florida

November 30, 2004