<PAGE>
 
     As filed with the Securities and Exchange Commission on July 3, 1996.
                                                      Registration No. 33-
=============================================================================== 

                       SECURITIES AND EXCHANGE COMMISSION
                            WASHINGTON, D.C.  20549
                                ---------------

                                    FORM S-8
            REGISTRATION STATEMENT UNDER THE SECURITIES ACT OF 1933

                         CATALINA MARKETING CORPORATION
             (Exact name of registrant as specified in its charter)

        DELAWARE                                         33-0499007
(State or other jurisdiction of                (IRS Employer Identification No.)
incorporation or organization)

       11300 9TH STREET NORTH                            33716-2329
       ST. PETERSBURG, FLORIDA                           (Zip Code)
(Address of Principal Executive Offices)


                         CATALINA MARKETING CORPORATION
                           DEFERRED COMPENSATION PLAN
                              (Full Title of Plan)

       Philip B. Livingston      Please address a copy of all communications to:
      Chief Financial Officer
   Catalina Marketing Corporation                  Barry A. Brooks
      11300 9th Street North              Paul, Hastings, Janofsky & Walker
   St. Petersburg, Florida 33716                 Thirty-First Floor
(Name and address of agent for service)           399 Park Avenue
                                               New York, NY 10022-4697
                                            Telephone:  (212) 318-6000
          (813) 579-5000
(Telephone number, including area code, 
       of agent for service)

     APPROXIMATE DATE OF COMMENCEMENT OF PROPOSED SALE TO PUBLIC:  By Catalina
Marketing Corporation in accordance with the terms of the Deferred Compensation
Plan after the effective date of this Registration Statement.

     If the only securities being registered on this Form are being offered
pursuant to dividend or interest reinvestment plans, please check the following
box.    [ ]

     If any of the securities being registered on this Form are to be offered on
a delayed or continuous basis pursuant to Rule 415 under the Securities Act of
1933, other than securities offered only in connection with dividend or interest
reinvestment plans, check the following box.    [X]
<PAGE>
 
                              CALCULATION OF REGISTRATION FEE
                              -------------------------------
=============================================================================== 
                                         PROPOSED       PROPOSED
TITLE OF                                 MAXIMUM        MAXIMUM
SECURITIES                 AMOUNT        OFFERING      AGGREGATE     AMOUNT OF
TO BE                      TO BE           PRICE        OFFERING    REGISTRATION
REGISTERED               REGISTERED(3)   PER SHARE (3)  PRICE (3)        FEE
- ------------------------------------------------------------------------------- 
DEFERRED COMPENSATION
 PLAN OBLIGATIONS (1)    $20,000,000         100%       $20,000,000     $6,897
 
COMMON STOCK
$0.01 PAR VALUE
PER SHARE (2)                350,000
=============================================================================== 
(1) The Registrant's Deferred Compensation Plan (the "Plan") Obligations are
    unsecured obligations of the Registrant to pay benefits in the future in
    accordance with the terms of the Plan to a select group of eligible
    employees and directors.

(2) Represents the presumed maximum number of shares of the Registrant's common
    stock, $0.01 par value per share (the "Common Stock"), that may be issued
    and sold by the Registrant under the Plan.  These shares will be issued for
    no additional consideration and, therefore, no additional fee is required.
    In accordance with Rule 416(a) under the Securities Act of 1933, as amended,
    this Registration Statement also covers such indeterminable number of
    additional shares as may become issuable to prevent dilution in the event of
    stock splits, stock dividends or similar transactions pursuant to the terms
    of the Plan.

(3) Estimated solely for the purpose of determining the registration fee.
<PAGE>
 
                                     PART I

              INFORMATION REQUIRED IN THE SECTION 10(a) PROSPECTUS

ITEM 1.   PLAN INFORMATION*

ITEM 2.   REGISTRANT INFORMATION AND EMPLOYEE PLAN ANNUAL INFORMATION*

   * Information required by Part I to be contained in the Section 10(a)
     prospectus is omitted from the registration statement in accordance with
     Rule 428 under the Securities Act of 1933 and the Note to Part I of Form S-
     8.


                                    PART II

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

ITEM 3.   INCORPORATION OF DOCUMENTS BY REFERENCE

          The following documents are incorporated herein by reference:

          (a) The Registrant's annual report on Form 10-K for the fiscal year
ended March 31, 1996 filed pursuant to the Securities Exchange Act of 1934 (the
"Exchange Act");

          (b) The Registrant's current report on Form 8-K dated April 25, 1996
and Amendment No. 1 thereto filed pursuant to the Exchange Act;

          (c)  All other reports filed pursuant to Section 13(a) or 15(d) of the
Exchange Act since the end of the fiscal year covered by the Registrant's annual
report referred to in (a) above; and

          (d) The description of the Registrant's common stock, $0.01 par value
per share (the "Common Stock"), contained in its registration statement on Form
8-A filed under Section 12 of the Exchange Act, including any amendments or
reports filed for the purpose of updating such description.

          All documents subsequently filed with the Commission by the Registrant
pursuant to Sections 13(a), 13(c), 14 and 15(d) of the Exchange Act prior to the
filing of a post-effective amendment to this Registration Statement which
indicates that all securities offered have been sold or which de-registers all
securities then remaining unsold, shall be deemed to be incorporated by
reference into this Registration Statement and to be a part hereof from the date
of filing of such documents.  Any statement contained in the documents
incorporated by reference herein shall be deemed to be modified or superseded
for purposes of this Registration Statement to the extent that a statement
contained herein or in any other subsequently filed document which also is or is
deemed to be incorporated by reference herein modifies or supersedes such
statement.  Any statement so modified or superseded shall not be deemed, except
as so modified or superseded, to constitute a part of this Registration
Statement.

ITEM 4.   DESCRIPTION OF SECURITIES

          Common Stock
          ------------

          The shares of the Registrant's Common Stock being offered pursuant to
the Deferred Compensation Plan (the "Plan") have been registered under Section
12 of the Exchange Act.
<PAGE>
 
     Deferred Compensation Plan Obligations
     --------------------------------------

     Pursuant to the terms of the Plan, eligible employees and directors (each a
"Participant") of the Registrant may defer a specified percentage of their
salary, bonus, commissions, director's fees, Option Profit (as defined in the
Plan) and stock grants received under the 1992 Director Grant Plan.  Such
amounts deferred under the Plan are referred to herein as "Deferred Compensation
Plan Obligations".  Deferred Compensation Plan Obligations of the Registrant
under the Plan will be unsecured general obligations of the Registrant to pay
the deferred compensation in the future in accordance with the terms of the Plan
and will rank equally with other unsecured and unsubordinated indebtedness of
the Registrant from time to time outstanding.  Other than deferred amounts
invested in Common Stock unit accounts created under the Plan, the amounts of
salary, bonus, commissions and directors fees to be deferred by a Participant,
together with any matching contributions made by the Registrant, will be
invested in one or more investment alternatives selected by the deferring
Participant in accordance with the terms of the Plan.  Investment alternatives
include a variety of stock and bond funds.  Upon a payment event, amounts
deferred together with vested matching contributions will be denominated and
paid in United States dollars.

     All stock grants and Option Profit deferred pursuant to the Plan will be
invested in Common Stock unit accounts maintained under the Plan.  Further, a
Participant may elect to deposit fifty percent of any deferred bonus and
commissions into a Common Stock unit account.  Directors may also elect to
invest deferred directors fees in Common Stock unit accounts.  All such amounts
invested in Common Stock unit accounts will be credited with an amount equal to
each dividend declared and paid on shares of the Registrant's Common Stock,
which amount shall be deemed invested in Common Stock units.  Such accounts
shall also be adjusted to take into account any stock dividend, stock split or
other similar transaction relating to the Registrant's Common Stock.  Common
Stock unit accounts will not entitle Participants to vote on matters presented
to the stockholders of the Registrant.  Upon a payment event under the Plan,
amounts invested in a Common Stock unit account will be paid in shares of Common
Stock of the Registrant.

     Generally, the Deferred Compensation Plan Obligations are not subject to
withdrawal, in whole or in part, by Participants except upon certain specified
events, including termination of employment, retirement, disability or death.
The Deferred Compensation Plan Obligations are not subject to redemption by the
Registrant at its option, or through operation of any mandatory or optional
sinking fund or analogous provisions.  The Registrant reserves the right to
amend or terminate the Plan at any time, except that no such event or
termination may adversely affect the right of a Participant to the balance of
his or her accounts as of the date of such amendment or termination.

     Generally, a Participant's right or the right of any other person to
receive payment of the Deferred Compensation Plan Obligations cannot be
assigned, alienated, sold, garnished, transferred, pledged or encumbered except
by a written designation by a beneficiary under the Plan.  However, if a
Participant is terminated for certain reasons as designated under the Plan, such
Participant will forfeit all matching contributions made by the Registrant under
the Plan which have not fully vested as of such time.

     The Deferred Compensation Plan Obligations are not convertible into another
security of the Company; provided that amounts deposited in Common Stock unit
accounts maintained under the Plan will be paid in shares of Common Stock.  The
Deferred Compensation Plan Obligations will not have the benefit of a negative
pledge or any other affirmative or negative covenant on the part of the
Registrant.  No trustee has been appointed having the authority to take action
with respect to the Deferred Compensation Plan Obligations, and each Participant
will be responsible for acting independently with respect to, among other
things, the giving of notices,
<PAGE>
 
responding to any requests for consent waivers or amendments pertaining to the
Deferred Compensation Plan Obligations, enforcing covenants and taking action
upon a default.

          The Registrant has established a "rabbi trust" to assist the
Registrant with its obligations to make payments under the Plan. Participants in
the Plan have no rights to any assets held by the rabbi trust, except as general
creditors of the Registrant. Assets of the rabbi trust will at all times be
subject to the claims of the Registrant's general creditors.

ITEM 5.   INTERESTS OF NAMED EXPERTS AND COUNSEL

          Not applicable.

ITEM 6.   INDEMNIFICATION OF DIRECTORS AND OFFICERS

          The Registrant's Restated Certificate of Incorporation and Restated
Bylaws include provisions to (i) eliminate the personal liability of its
directors for monetary damages resulting from breaches of their fiduciary duty
to the extent permitted by the General Corporation Law of Delaware (the
"Delaware Law") and (ii) require the Registrant to indemnify its directors and
officers to the fullest extent permitted by the Delaware Law, including under
circumstances in which indemnification is otherwise discretionary. The
Registrant believes that these provisions are necessary to attract and retain
qualified persons as directors and officers.

          These provisions do not eliminate the directors' duty of care, and, in
appropriate circumstances, equitable remedies such as injunctive or other forms
of non-monetary relief remain available under the Delaware Law.  In addition,
each director is subject to liability for breach of the director's duty of
loyalty to the Registrant, for acts or omissions not in good faith or involving
intentional misconduct, for knowing violations of law, for actions leading to
improper personal benefit to the director and for payment of dividends or
approval of stock repurchases or redemptions that are unlawful under the
Delaware Law.  These provisions also do not affect a director's responsibilities
under any other laws, such as the federal securities laws or state or federal
environmental laws.

          As permitted by its Restated Bylaws, the Registrant has entered into
agreements with its directors and officers that require the Registrant to
indemnify such persons against expenses, judgments, fines, settlements and other
amounts incurred (including expenses of a derivative action) in connection with
any proceeding to which any such person may be made a party by reason of the
fact that such person is or was a director or officer of the Registrant,
provided such person acted in good faith and in a manner such person reasonably
believed to be in or not opposed to the best interests of the Registrant.

ITEM 7.   EXEMPTION FROM REGISTRATION CLAIMED

          Not applicable.

ITEM 8.   EXHIBITS

          The exhibits filed as part of this Registration Statement are as
follows:


Exhibit Number           Description of Exhibit
- --------------           ----------------------

     4    The Catalina Marketing Corporation Deferred Compensation Plan.

     5    Opinion of Paul, Hastings, Janofsky & Walker as to the legality of the
          securities registered hereunder.
<PAGE>
 
     23.1 Consent of Arthur Andersen LLP, Independent Public Accountants,
          relating to the use of their report contained in Registrant's Annual
          Report on Form 10-K for the fiscal year ended March 31, 1996.

     23.2 Consent of Paul, Hastings, Janofsky & Walker to the filing and use of
          their opinion relating to the legality of the securities.  Such
          consent is contained in their opinion filed as Exhibit 5 to this
          Registration Statement.

     24   Power of Attorney authorizing Philip B. Livingston and George W. Off
          to sign amendments to this Registration Statement on behalf of
          officers and directors of the Registrant (contained on signature page
          of Registration Statement).

ITEM 9.   UNDERTAKINGS

     (a) The undersigned registrant hereby undertakes:

          (1)  To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement to include any
material information with respect to the plan of distribution not previously
disclosed in the registration statement or any material change to such
information in the registration statement.

          (2)  That, for purposes of determining any liability under the
Securities Act of 1933, each such post-effective amendment shall be deemed to be
a new registration statement relating to the securities offered therein, and the
offering of such securities at that time shall be deemed the initial bona fide
offering thereof.

          (3)  To remove from registration by means of a post-effective
amendment any of the securities being registered which remain unsold at the
termination of the offering.

     (b)  The undersigned registrant hereby undertakes that, for purposes of
determining any liability under the Securities Act of 1933, each filing of the
registrant's annual report pursuant to Section 13(a) or 15(d) of the Securities
Exchange Act of 1934 that is incorporated by reference in the registration
statement shall be deemed to be a new registration statement relating to the
securities offered therein, and the offering of such securities at that time
shall be deemed to be the initial bona fide offering thereof.

     (c)  Insofar as indemnification for liabilities arising under the
Securities Act of 1933 may be permitted to directors, officers and controlling
persons of the registrant pursuant to provisions pursuant to which the
directors, officers or controlling persons may be indemnified by the registrant
or otherwise, the registrant has been advised that in the opinion of the
Securities and Exchange Commission such indemnification is against public policy
as expressed in the Act and is, therefore, unenforceable.  In the event that a
claim for indemnification against such liabilities (other than the payment by
the registrant of expenses incurred or paid by a director, officer or
controlling person of the registrant in the successful defense of any action,
suit or proceeding) is asserted by such director, officer or controlling person
in connection with the securities being registered, the registrant will submit
to a court of appropriate jurisdiction the question whether such indemnification
by it is against public policy as expressed in the Act and will be governed by
the final adjudication of such issue.
<PAGE>
 
                                   SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, the Registrant
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of St. Petersburg, State of Florida, on this 1st day of
July, 1996.


                                    CATALINA MARKETING CORPORATION
                                    (REGISTRANT)



                                    BY:        /S/ PHILIP B. LIVINGSTON
                                       -----------------------------------------
                                                 Philip B. Livingston,
                                       Senior Vice President and Chief Financial
                                       Officer


                               POWER OF ATTORNEY
                               -----------------

     KNOW ALL MEN BY THESE PRESENTS, that each person whose signature appears
below constitutes and appoints Philip B. Livingston and George W. Off, jointly
and severally, his or her attorneys-in-fact, each with power of substitution for
him or her in any and all capacities, to sign any amendments to this
Registration Statement, and to file the same, with the exhibits thereto, and
other documents in connection therewith, with the Securities and Exchange
Commission hereby ratifying and confirming all that each of said attorneys-in-
fact, or his substitute or substitutes, may do or cause to be done by virtue
hereof.

     Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed below by the following persons in the
capacities and on the date indicated.
 
         SIGNATURE                         TITLE                   DATE
- ----------------------------  -------------------------------  ------------

/s/ Tommy D. Greer             Chairman of the Board           July 1, 1996
- ----------------------------
Tommy D. Greer

/s/ George W. Off              Chief Executive Officer,        July 1, 1996
- ----------------------------   President and Director
George W. Off                  (Principal Executive and
                               Operating Officer)

/s/ Phillip B. Livingston      Senior Vice President and       July 1, 1996
- ----------------------------   Chief
Philip B. Livingston           Financial Officer
 
/s/ Robert A. Busch            Corporate Controller and        July 1, 1996
- ----------------------------   Principal Accounting Officer
Robert A. Busch

/s/ Frank H. Barker            Director                        July 1, 1996
- ----------------------------
Frank H. Barker

/s/ Frederick W. Beinecke      Director                        July 1, 1996
- ----------------------------
Frederick W. Beinecke

/s/ Patrick W. Collins         Director                        July 1, 1996
- ----------------------------
Patrick W. Collins
<PAGE>
 
/s/ Stephen I. D'Agostino                Director              July 1, 1996
- ----------------------------
Stephen I. D'Agostino

                                         Director                    , 1996
- ----------------------------                                   ------
Thomas G. Mendell

/s/ Helene Monat                         Director              July 1, 1996
- ----------------------------
Helene Monat
                                         Director                    , 1996
- ----------------------------                                   ------
Thomas W. Smith

/s/ Michael B. Wilson                    Director              July 1, 1996
- ----------------------------
Michael B. Wilson
<PAGE>
 
                                 EXHIBIT  INDEX
                                 --------------


  Exhibit            Description
  -------            -----------

     4    The Catalina Marketing Corporation Deferred Compensation Plan.

     5    Opinion of Paul, Hastings, Janofsky & Walker as to the legality of the
          Securities registered hereunder.

     23.1 Consent of Arthur Andersen LLP, Independent Public Accountants,
          relating to the use of their report contained in Registrant's Annual
          Report on Form 10-K for the fiscal year ended March 31, 1996.

     23.2 Consent of Paul, Hastings, Janofsky & Walker to the filing and use of
          their opinion relating to the legality of the securities.  Such
          consent is contained in their opinion filed as Exhibit 5 to this
          Registration Statement.

     24   Power of Attorney authorizing Philip B. Livingston and George W. Off
          to sign amendments to this Registration Statement on behalf of
          officers and directors of the Registrant (contained on signature page
          of Registration Statement).
[{"type": "S-8", "sequence": "1", "description": "FORM S-8", "secsgml_size_bytes": 22978}]
{"company-data": {"conformed-name": "CATALINA MARKETING CORP/DE", "cik": "0000883977", "assigned-sic": "7311", "irs-number": "330499007", "state-of-incorporation": "DE", "fiscal-year-end": "0331"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-07525", "film-number": "96590874"}, "business-address": {"street1": "11300 9TH ST NORTH", "city": "ST PETERSBURG", "state": "FL", "zip": "33716", "phone": "8135795000"}, "mail-address": {"street1": "11300 9TH STREET NORTH", "city": "ST PETERSBURG", "state": "FL", "zip": "33716-2329"}}
As filed with the Securities and Exchange Commission on July 3, 1996.
                                                      Registration No. 33-
=============================================================================== 

                       SECURITIES AND EXCHANGE COMMISSION
                            WASHINGTON, D.C.  20549
                                ---------------

                                    FORM S-8
            REGISTRATION STATEMENT UNDER THE SECURITIES ACT OF 1933

                         CATALINA MARKETING CORPORATION
             (Exact name of registrant as specified in its charter)

        DELAWARE                                         33-0499007
(State or other jurisdiction of                (IRS Employer Identification No.)
incorporation or organization)

       11300 9TH STREET NORTH                            33716-2329
       ST. PETERSBURG, FLORIDA                           (Zip Code)
(Address of Principal Executive Offices)

                         CATALINA MARKETING CORPORATION
                           DEFERRED COMPENSATION PLAN
                              (Full Title of Plan)

       Philip B. Livingston      Please address a copy of all communications to:
      Chief Financial Officer
   Catalina Marketing Corporation                  Barry A. Brooks
      11300 9th Street North              Paul, Hastings, Janofsky & Walker
   St. Petersburg, Florida 33716                 Thirty-First Floor
(Name and address of agent for service)           399 Park Avenue
                                               New York, NY 10022-4697
                                            Telephone:  (212) 318-6000
          (813) 579-5000
(Telephone number, including area code, 
       of agent for service)

     APPROXIMATE DATE OF COMMENCEMENT OF PROPOSED SALE TO PUBLIC:  By Catalina
Marketing Corporation in accordance with the terms of the Deferred Compensation
Plan after the effective date of this Registration Statement.

     If the only securities being registered on this Form are being offered
pursuant to dividend or interest reinvestment plans, please check the following
box.    [ ]

     If any of the securities being registered on this Form are to be offered on
a delayed or continuous basis pursuant to Rule 415 under the Securities Act of
1933, other than securities offered only in connection with dividend or interest
reinvestment plans, check the following box.    [X]
CALCULATION OF REGISTRATION FEE
                              -------------------------------
=============================================================================== 
                                         PROPOSED       PROPOSED
TITLE OF                                 MAXIMUM        MAXIMUM
SECURITIES                 AMOUNT        OFFERING      AGGREGATE     AMOUNT OF
TO BE                      TO BE           PRICE        OFFERING    REGISTRATION
REGISTERED               REGISTERED(3)   PER SHARE (3)  PRICE (3)        FEE
- ------------------------------------------------------------------------------- 
DEFERRED COMPENSATION
 PLAN OBLIGATIONS (1)    $20,000,000         100%       $20,000,000     $6,897
 
COMMON STOCK
$0.01 PAR VALUE
PER SHARE (2)                350,000
=============================================================================== 
(1) The Registrant's Deferred Compensation Plan (the "Plan") Obligations are
    unsecured obligations of the Registrant to pay benefits in the future in
    accordance with the terms of the Plan to a select group of eligible
    employees and directors.

(2) Represents the presumed maximum number of shares of the Registrant's common
    stock, $0.01 par value per share (the "Common Stock"), that may be issued
    and sold by the Registrant under the Plan.  These shares will be issued for
    no additional consideration and, therefore, no additional fee is required.
    In accordance with Rule 416(a) under the Securities Act of 1933, as amended,
    this Registration Statement also covers such indeterminable number of
    additional shares as may become issuable to prevent dilution in the event of
    stock splits, stock dividends or similar transactions pursuant to the terms
    of the Plan.

(3) Estimated solely for the purpose of determining the registration fee.
PART I

              INFORMATION REQUIRED IN THE SECTION 10(a) PROSPECTUS

ITEM 1.   PLAN INFORMATION*

ITEM 2.   REGISTRANT INFORMATION AND EMPLOYEE PLAN ANNUAL INFORMATION*

   * Information required by Part I to be contained in the Section 10(a)
     prospectus is omitted from the registration statement in accordance with
     Rule 428 under the Securities Act of 1933 and the Note to Part I of Form S-
     8.

                                    PART II

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

ITEM 3.   INCORPORATION OF DOCUMENTS BY REFERENCE

          The following documents are incorporated herein by reference:

          (a) The Registrant's annual report on Form 10-K for the fiscal year
ended March 31, 1996 filed pursuant to the Securities Exchange Act of 1934 (the
"Exchange Act");

          (b) The Registrant's current report on Form 8-K dated April 25, 1996
and Amendment No. 1 thereto filed pursuant to the Exchange Act;

          (c)  All other reports filed pursuant to Section 13(a) or 15(d) of the
Exchange Act since the end of the fiscal year covered by the Registrant's annual
report referred to in (a) above; and

          (d) The description of the Registrant's common stock, $0.01 par value
per share (the "Common Stock"), contained in its registration statement on Form
8-A filed under Section 12 of the Exchange Act, including any amendments or
reports filed for the purpose of updating such description.

          All documents subsequently filed with the Commission by the Registrant
pursuant to Sections 13(a), 13(c), 14 and 15(d) of the Exchange Act prior to the
filing of a post-effective amendment to this Registration Statement which
indicates that all securities offered have been sold or which de-registers all
securities then remaining unsold, shall be deemed to be incorporated by
reference into this Registration Statement and to be a part hereof from the date
of filing of such documents.  Any statement contained in the documents
incorporated by reference herein shall be deemed to be modified or superseded
for purposes of this Registration Statement to the extent that a statement
contained herein or in any other subsequently filed document which also is or is
deemed to be incorporated by reference herein modifies or supersedes such
statement.  Any statement so modified or superseded shall not be deemed, except
as so modified or superseded, to constitute a part of this Registration
Statement.

ITEM 4.   DESCRIPTION OF SECURITIES

          Common Stock
          ------------

          The shares of the Registrant's Common Stock being offered pursuant to
the Deferred Compensation Plan (the "Plan") have been registered under Section
12 of the Exchange Act.
Deferred Compensation Plan Obligations
     --------------------------------------

     Pursuant to the terms of the Plan, eligible employees and directors (each a
"Participant") of the Registrant may defer a specified percentage of their
salary, bonus, commissions, director's fees, Option Profit (as defined in the
Plan) and stock grants received under the 1992 Director Grant Plan.  Such
amounts deferred under the Plan are referred to herein as "Deferred Compensation
Plan Obligations".  Deferred Compensation Plan Obligations of the Registrant
under the Plan will be unsecured general obligations of the Registrant to pay
the deferred compensation in the future in accordance with the terms of the Plan
and will rank equally with other unsecured and unsubordinated indebtedness of
the Registrant from time to time outstanding.  Other than deferred amounts
invested in Common Stock unit accounts created under the Plan, the amounts of
salary, bonus, commissions and directors fees to be deferred by a Participant,
together with any matching contributions made by the Registrant, will be
invested in one or more investment alternatives selected by the deferring
Participant in accordance with the terms of the Plan.  Investment alternatives
include a variety of stock and bond funds.  Upon a payment event, amounts
deferred together with vested matching contributions will be denominated and
paid in United States dollars.

     All stock grants and Option Profit deferred pursuant to the Plan will be
invested in Common Stock unit accounts maintained under the Plan.  Further, a
Participant may elect to deposit fifty percent of any deferred bonus and
commissions into a Common Stock unit account.  Directors may also elect to
invest deferred directors fees in Common Stock unit accounts.  All such amounts
invested in Common Stock unit accounts will be credited with an amount equal to
each dividend declared and paid on shares of the Registrant's Common Stock,
which amount shall be deemed invested in Common Stock units.  Such accounts
shall also be adjusted to take into account any stock dividend, stock split or
other similar transaction relating to the Registrant's Common Stock.  Common
Stock unit accounts will not entitle Participants to vote on matters presented
to the stockholders of the Registrant.  Upon a payment event under the Plan,
amounts invested in a Common Stock unit account will be paid in shares of Common
Stock of the Registrant.

     Generally, the Deferred Compensation Plan Obligations are not subject to
withdrawal, in whole or in part, by Participants except upon certain specified
events, including termination of employment, retirement, disability or death.
The Deferred Compensation Plan Obligations are not subject to redemption by the
Registrant at its option, or through operation of any mandatory or optional
sinking fund or analogous provisions.  The Registrant reserves the right to
amend or terminate the Plan at any time, except that no such event or
termination may adversely affect the right of a Participant to the balance of
his or her accounts as of the date of such amendment or termination.

     Generally, a Participant's right or the right of any other person to
receive payment of the Deferred Compensation Plan Obligations cannot be
assigned, alienated, sold, garnished, transferred, pledged or encumbered except
by a written designation by a beneficiary under the Plan.  However, if a
Participant is terminated for certain reasons as designated under the Plan, such
Participant will forfeit all matching contributions made by the Registrant under
the Plan which have not fully vested as of such time.

     The Deferred Compensation Plan Obligations are not convertible into another
security of the Company; provided that amounts deposited in Common Stock unit
accounts maintained under the Plan will be paid in shares of Common Stock.  The
Deferred Compensation Plan Obligations will not have the benefit of a negative
pledge or any other affirmative or negative covenant on the part of the
Registrant.  No trustee has been appointed having the authority to take action
with respect to the Deferred Compensation Plan Obligations, and each Participant
will be responsible for acting independently with respect to, among other
things, the giving of notices,
responding to any requests for consent waivers or amendments pertaining to the
Deferred Compensation Plan Obligations, enforcing covenants and taking action
upon a default.

          The Registrant has established a "rabbi trust" to assist the
Registrant with its obligations to make payments under the Plan. Participants in
the Plan have no rights to any assets held by the rabbi trust, except as general
creditors of the Registrant. Assets of the rabbi trust will at all times be
subject to the claims of the Registrant's general creditors.

ITEM 5.   INTERESTS OF NAMED EXPERTS AND COUNSEL

          Not applicable.

ITEM 6.   INDEMNIFICATION OF DIRECTORS AND OFFICERS

          The Registrant's Restated Certificate of Incorporation and Restated
Bylaws include provisions to (i) eliminate the personal liability of its
directors for monetary damages resulting from breaches of their fiduciary duty
to the extent permitted by the General Corporation Law of Delaware (the
"Delaware Law") and (ii) require the Registrant to indemnify its directors and
officers to the fullest extent permitted by the Delaware Law, including under
circumstances in which indemnification is otherwise discretionary. The
Registrant believes that these provisions are necessary to attract and retain
qualified persons as directors and officers.

          These provisions do not eliminate the directors' duty of care, and, in
appropriate circumstances, equitable remedies such as injunctive or other forms
of non-monetary relief remain available under the Delaware Law.  In addition,
each director is subject to liability for breach of the director's duty of
loyalty to the Registrant, for acts or omissions not in good faith or involving
intentional misconduct, for knowing violations of law, for actions leading to
improper personal benefit to the director and for payment of dividends or
approval of stock repurchases or redemptions that are unlawful under the
Delaware Law.  These provisions also do not affect a director's responsibilities
under any other laws, such as the federal securities laws or state or federal
environmental laws.

          As permitted by its Restated Bylaws, the Registrant has entered into
agreements with its directors and officers that require the Registrant to
indemnify such persons against expenses, judgments, fines, settlements and other
amounts incurred (including expenses of a derivative action) in connection with
any proceeding to which any such person may be made a party by reason of the
fact that such person is or was a director or officer of the Registrant,
provided such person acted in good faith and in a manner such person reasonably
believed to be in or not opposed to the best interests of the Registrant.

ITEM 7.   EXEMPTION FROM REGISTRATION CLAIMED

          Not applicable.

ITEM 8.   EXHIBITS

          The exhibits filed as part of this Registration Statement are as
follows:

Exhibit Number           Description of Exhibit
- --------------           ----------------------

     4    The Catalina Marketing Corporation Deferred Compensation Plan.

     5    Opinion of Paul, Hastings, Janofsky & Walker as to the legality of the
          securities registered hereunder.
23.1 Consent of Arthur Andersen LLP, Independent Public Accountants,
          relating to the use of their report contained in Registrant's Annual
          Report on Form 10-K for the fiscal year ended March 31, 1996.

     23.2 Consent of Paul, Hastings, Janofsky & Walker to the filing and use of
          their opinion relating to the legality of the securities.  Such
          consent is contained in their opinion filed as Exhibit 5 to this
          Registration Statement.

     24   Power of Attorney authorizing Philip B. Livingston and George W. Off
          to sign amendments to this Registration Statement on behalf of
          officers and directors of the Registrant (contained on signature page
          of Registration Statement).

ITEM 9.   UNDERTAKINGS

     (a) The undersigned registrant hereby undertakes:

          (1)  To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement to include any
material information with respect to the plan of distribution not previously
disclosed in the registration statement or any material change to such
information in the registration statement.

          (2)  That, for purposes of determining any liability under the
Securities Act of 1933, each such post-effective amendment shall be deemed to be
a new registration statement relating to the securities offered therein, and the
offering of such securities at that time shall be deemed the initial bona fide
offering thereof.

          (3)  To remove from registration by means of a post-effective
amendment any of the securities being registered which remain unsold at the
termination of the offering.

     (b)  The undersigned registrant hereby undertakes that, for purposes of
determining any liability under the Securities Act of 1933, each filing of the
registrant's annual report pursuant to Section 13(a) or 15(d) of the Securities
Exchange Act of 1934 that is incorporated by reference in the registration
statement shall be deemed to be a new registration statement relating to the
securities offered therein, and the offering of such securities at that time
shall be deemed to be the initial bona fide offering thereof.

     (c)  Insofar as indemnification for liabilities arising under the
Securities Act of 1933 may be permitted to directors, officers and controlling
persons of the registrant pursuant to provisions pursuant to which the
directors, officers or controlling persons may be indemnified by the registrant
or otherwise, the registrant has been advised that in the opinion of the
Securities and Exchange Commission such indemnification is against public policy
as expressed in the Act and is, therefore, unenforceable.  In the event that a
claim for indemnification against such liabilities (other than the payment by
the registrant of expenses incurred or paid by a director, officer or
controlling person of the registrant in the successful defense of any action,
suit or proceeding) is asserted by such director, officer or controlling person
in connection with the securities being registered, the registrant will submit
to a court of appropriate jurisdiction the question whether such indemnification
by it is against public policy as expressed in the Act and will be governed by
the final adjudication of such issue.
SIGNATURES

     Pursuant to the requirements of the Securities Act of 1933, the Registrant
certifies that it has reasonable grounds to believe that it meets all of the
requirements for filing on Form S-8 and has duly caused this Registration
Statement to be signed on its behalf by the undersigned, thereunto duly
authorized, in the City of St. Petersburg, State of Florida, on this 1st day of
July, 1996.

                                    CATALINA MARKETING CORPORATION
                                    (REGISTRANT)

                                    BY:        /S/ PHILIP B. LIVINGSTON
                                       -----------------------------------------
                                                 Philip B. Livingston,
                                       Senior Vice President and Chief Financial
                                       Officer

                               POWER OF ATTORNEY
                               -----------------

     KNOW ALL MEN BY THESE PRESENTS, that each person whose signature appears
below constitutes and appoints Philip B. Livingston and George W. Off, jointly
and severally, his or her attorneys-in-fact, each with power of substitution for
him or her in any and all capacities, to sign any amendments to this
Registration Statement, and to file the same, with the exhibits thereto, and
other documents in connection therewith, with the Securities and Exchange
Commission hereby ratifying and confirming all that each of said attorneys-in-
fact, or his substitute or substitutes, may do or cause to be done by virtue
hereof.

     Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed below by the following persons in the
capacities and on the date indicated.
 
         SIGNATURE                         TITLE                   DATE
- ----------------------------  -------------------------------  ------------

/s/ Tommy D. Greer             Chairman of the Board           July 1, 1996
- ----------------------------
Tommy D. Greer

/s/ George W. Off              Chief Executive Officer,        July 1, 1996
- ----------------------------   President and Director
George W. Off                  (Principal Executive and
                               Operating Officer)

/s/ Phillip B. Livingston      Senior Vice President and       July 1, 1996
- ----------------------------   Chief
Philip B. Livingston           Financial Officer
 
/s/ Robert A. Busch            Corporate Controller and        July 1, 1996
- ----------------------------   Principal Accounting Officer
Robert A. Busch

/s/ Frank H. Barker            Director                        July 1, 1996
- ----------------------------
Frank H. Barker

/s/ Frederick W. Beinecke      Director                        July 1, 1996
- ----------------------------
Frederick W. Beinecke

/s/ Patrick W. Collins         Director                        July 1, 1996
- ----------------------------
Patrick W. Collins
/s/ Stephen I. D'Agostino                Director              July 1, 1996
- ----------------------------
Stephen I. D'Agostino

                                         Director                    , 1996
- ----------------------------                                   ------
Thomas G. Mendell

/s/ Helene Monat                         Director              July 1, 1996
- ----------------------------
Helene Monat
                                         Director                    , 1996
- ----------------------------                                   ------
Thomas W. Smith

/s/ Michael B. Wilson                    Director              July 1, 1996
- ----------------------------
Michael B. Wilson
EXHIBIT  INDEX
                                 --------------

  Exhibit            Description
  -------            -----------

     4    The Catalina Marketing Corporation Deferred Compensation Plan.

     5    Opinion of Paul, Hastings, Janofsky & Walker as to the legality of the
          Securities registered hereunder.

     23.1 Consent of Arthur Andersen LLP, Independent Public Accountants,
          relating to the use of their report contained in Registrant's Annual
          Report on Form 10-K for the fiscal year ended March 31, 1996.

     23.2 Consent of Paul, Hastings, Janofsky & Walker to the filing and use of
          their opinion relating to the legality of the securities.  Such
          consent is contained in their opinion filed as Exhibit 5 to this
          Registration Statement.

     24   Power of Attorney authorizing Philip B. Livingston and George W. Off
          to sign amendments to this Registration Statement on behalf of
          officers and directors of the Registrant (contained on signature page
          of Registration Statement).