<PAGE>

    As filed with the Securities and Exchange Commission on October 22, 1999
                                                     Registration No. 333-______

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

                       SECURITIES AND EXCHANGE COMMISSION
                              Washington, DC 20549
                               ------------------

                                    FORM S-8
                             REGISTRATION STATEMENT
                        Under The Securities Act of 1933
                               ------------------

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


                   DELAWARE                            52-0278528
         (State or other jurisdiction               (I.R.S. Employer
       of incorporation or organization)           Identification No.)

            8100 34th Avenue South                        55425
            Minneapolis, Minnesota                     (Zip Code)
   (Address of principal executive offices)


                 CERIDIAN CORPORATION 1999 STOCK INCENTIVE PLAN
                            (Full title of the plan)

                               William E. McDonald
                 Associate General Counsel and Deputy Secretary
                              Ceridian Corporation
                             8100 34th Avenue South
                          Minneapolis, Minnesota 55425
                     (Name and address of agent for service)

                                 (612) 853-8100
          (Telephone number, including area code, of agent for service)

                       CALCULATION OF REGISTRATION FEE (1)
<TABLE>
<CAPTION>
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
                                             Proposed                Proposed
  Title of                                   maximum                 maximum
securities             Amount to             offering                aggregate              Amount of
     to be                 be                price per               offering              registration
registered           Registered (2)          share                   price                     fee
---------------------------------------------------------------------------------------------------------
<S>                  <C>                     <C>                     <C>                  <C>
Common Stock
($.50 par value)     3,264,000 shares             $19.9375 (3)        $ 65,076,000        $     18,092
                         7,000 shares               $27.00 (3)        $    189,000        $         53
                        20,500 shares               $28.50 (3)        $    584,250        $        163
                       142,500 shares               $30.75 (3)        $  4,381,875        $      1,219
                        14,500 shares             $32.1825 (3)        $    466,646        $        130
                         3,500 shares             $31.3125 (3)        $    109,594        $         31
                        10,000 shares             $32.5625 (3)        $    325,625        $         91
                     6,538,000 shares              $17.875 (4)        $116,866,750        $     32,489
                    -----------------                                 ------------        ------------
         Total      10,000,000 shares                                 $187,999,740        $     52,268
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
</TABLE>

(1)    This Registration Statement is also deemed, pursuant to Instruction E to
       Form S-8, to relate to 2,457,462 shares of the 3,000,000 shares that had
       been previously registered on Form S-8 (File No. 333-28069) in connection
       with a predecessor plan, with respect to which a fee of $32,446 has been
       previously paid.
(2)    In addition, pursuant to Rule 416(a) under the Securities Act of 1933, as
       amended (the "Act"), this Registration Statement also covers an
       indeterminate number of additional shares that may be offered or issued
       as a result of the anti-dilution provisions of the above-referenced plan.
(3)    Calculated pursuant to Rule 457(h) for the purpose of calculating the
       registration fee, based upon the price at which outstanding options may
       be exercised.
(4)    Estimated solely for the purpose of calculating the registration fee in
       accordance with Rule 457(h)(1) and (c), based upon the average of the
       reported high and low prices of the Common Stock as reported on the
       Consolidated Transaction Reporting System of the New York Stock Exchange
       on October 19, 1999.
<PAGE>

                                EXPLANATORY NOTE

         On May 30, 1997, a total of 3,000,000 shares of Common Stock of
Ceridian Corporation (the "Company") to be issued in connection with the
Company's 1993 Long-Term Incentive Plan (Amended and Restated on May 14, 1997)
(the "1993 Plan"), were registered with the Securities and Exchange Commission
(the "Commission") by a Registration Statement on Form S-8 (File No. 333-28069).
On May 20, 1999, the stockholders of the Company approved the 1999 Stock
Incentive Plan (the "1999 Plan"), which replaces the 1993 Plan. Both the 1999
Plan and the 1993 Plan are long term incentive plans. As of October 4, 1999, two
million four hundred fifty seven thousand four hundred sixty two (2,457,462)
shares of such registered shares of Common Stock of the Company under the 1993
Plan had not been issued under the 1993 Plan and, pursuant to Instruction E to
Form S-8 and the telephonic interpretation of the Commission pertaining to "Form
S-8"setforth in the Division of Corporation Finance's Manual of
Publicly-Available Telephone Interpretations (July 1997), are carried forward
to, and deemed covered by this Registration Statement on Form S-8 in connection
with the 1999 Plan.


                                    PART II.

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

Item 3.    INCORPORATION OF DOCUMENTS BY REFERENCE.

         The following documents, which have been filed by Ceridian Corporation
(the "Company") with the Securities and Exchange Commission, are incorporated by
reference in this Registration Statement, as of their respective dates:

(a)      The Company's Annual Report on Form 10-K for the fiscal year ended
         December 31, 1998;

(b)      The Company's Quarterly Report on Form 10-Q for the quarters ending
         March 31, 1999 and June 30, 1999;

(c)      The Company's Current Report on Form 8-K as filed with the Securities
         and Exchange Commission on June 21, 1999, as amended and filed on
         August 20, 1999;

(d)      All other reports filed by the Company pursuant to Sections 13(a) or
         15(d) of the Securities Exchange Act of 1934, as amended (the "Exchange
         Act") since December 31, 1998; and

(e)      The description of the Company's capital stock contained in the
         Company's Registration Statement on Form S-4 (File No. 33-64089),
         including any amendments or reports filed for the purpose of updating
         such description.

         All documents filed by the Company pursuant to Sections 13(a), 13(c),
14 and 15(d) of the Exchange Act, subsequent to the date hereof and prior to the
filing of a post-effective amendment which indicates that all securities offered
hereby have been sold or which deregisters all securities remaining unsold,
shall be deemed to be incorporated by reference herein and to be a part hereof
from the respective dates of filing of such documents.

                                       II-1

<PAGE>

Item 4.  DESCRIPTION OF SECURITIES.

         The Company's Common Stock is registered under Section 12 of the
Exchange Act.


Item 5.  INTERESTS OF NAMED EXPERTS AND COUNSEL.

         William E. McDonald, Associate General Counsel and Deputy Secretary for
the Company, has provided an opinion as to the legality of the securities being
registered hereby. As a result of awards under stock-based compensation plans
maintained by the Company, including the Employee Stock Purchase Plan, Mr.
McDonald holds options to acquire shares of common stock of the Company with a
value that may exceed $50,000 upon vesting.

Item 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

         Section 145 of the Delaware General Corporation Law of the State of
Delaware ("DGCL") grants each corporation organized thereunder, such as the
Company, the power to indemnify its directors and officers against liability for
certain of their acts. Section 102(b)(7) of the DGCL permits a provision in the
certificate of incorporation of each corporation organized thereunder
eliminating or limiting, with certain exceptions, the personal liability of a
director to the corporation or its stockholders for monetary damages for breach
of fiduciary duty as a director. The Company's certificate of incorporation
contains such a provision. The foregoing statements are subject to the detailed
provisions of Sections 145 and 102(b)(7) of the DGCL.

         Article VI of the Company's Bylaws provides that the Company shall
indemnify its officers, directors and employees to the fullest extent permitted
by the DGCL in connection with proceedings with which any such person is
involved by virtue of his or her status as an officer, director or employee. The
Company has also by contract agreed to indemnify its directors against damages,
judgments, settlements and costs arising out of any actions against the
directors brought by reason of the fact that they are or were directors. The
Company maintains directors' and officers' liability insurance, including a
reimbursement policy in favor of the Company.

Item 7.  EXEMPTION FROM REGISTRATION CLAIMED.

         Not applicable.

Item 8.  EXHIBITS.

         The following is a complete list of Exhibits filed or incorporated by
reference as part of this registration statement:

<TABLE>
<CAPTION>
         Exhibit:    Description:
         --------    ------------
         <C>         <S>
         5.01        Opinion and consent of William E. McDonald.

         23.01       Consent of KPMG LLP.

         23.02       Consent of Grant Thornton LLP.

         23.03       Consent of William E. McDonald (included in Exhibit 5.01).

         24.01       Power of Attorney (included on page II-4 of the
                     Registration Statement).
</TABLE>

Item 9   UNDERTAKINGS.

A.       The undersigned registrant hereby undertakes:

                                       II-2

<PAGE>

         (1)      To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement:

                  (i)      To include any prospectus required by Section
                           10(a)(3) of the Securities Act of 1933;

                  (ii)     To reflect in the prospectus any facts or events
                           arising after the effective date of the registration
                           statement (or the most recent post-effective
                           amendment thereof) which, individually or in the
                           aggregate, represent a fundamental change in the
                           information set forth in the registration statement.
                           Notwithstanding the foregoing, any increase or
                           decrease in volume of securities offered (if the
                           total dollar value of securities would not exceed
                           that which was registered) and any deviation from the
                           low or high end of the estimated maximum offering
                           range may be reflected in the form of prospectus
                           filed with the Securities and Exchange Commission
                           pursuant to Rule 424(b) if, in the aggregate, the
                           changes in volume and price represent no more than a
                           20% change in the maximum aggregate offering price
                           set forth in the "Calculation of Registration Fee"
                           table in the effective Registration Statement;

                  (iii)    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;

PROVIDED, HOWEVER, that paragraphs A(1)(i) and A(1)(ii) above will not apply if
the information required to be included in a post-effective amendment by those
paragraphs is contained in periodic reports filed by the registrant pursuant to
Section 13 or Section 15(d) of the Securities Exchange Act of 1934 that are
incorporated by reference in the registration statement.


         (2)      That, for the purpose 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 to be 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 Section 15(d) of the
Exchange Act 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 the foregoing provisions, 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
Securities Act of 1933 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 other
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, unless
in the opinion of its counsel the matter has been settled by controlling
precedent, submit to a court of appropriate jurisdiction the question whether
such indemnification by it is against public policy as expressed in the
Securities Act of 1933 and will be governed by the final adjudication of such
issue.

                                       II-3
<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 Minneapolis, State of Minnesota, on the 22nd day of
October, 1999.

                               CERIDIAN CORPORATION


                               By:  /s/ Lawrence Perlman
                                    --------------------------------
                                    Lawrence Perlman
                                    Chairman of the Board and
                                    Chief Executive Officer


                                POWER OF ATTORNEY

         Each person whose signature appears below constitutes and appoints
Lawrence Perlman, John R. Eickhoff and Gary M. Nelson, and each of them, his or
her true and lawful attorney-in-fact and agent with full powers of substitution
and resubstitution, for and in his or her name, place and stead, in any and all
capacities, to sign any or all amendments (including post-effective amendments)
to this registration statement, and to file the same, with all exhibits thereto,
and other documents in connection therewith, with the Securities and Exchange
Commission, granting unto said attorney-in-fact and agent full power and
authority to do and perform each and every act and thing requisite or necessary
to be done in and about the premises, as fully to all intents and purposes as he
or she might or could do in person, hereby ratifying and confirming all that
said attorney-in-fact and agent or his substitute or substitutes, may lawfully
do or cause to be done by virtue thereof.

         Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed by the following persons in the
capacities indicated on the 22nd day of October, 1999.


<TABLE>
<CAPTION>
    Signature                                Title
    ---------                                -----
<S>                         <C>
/s/ Lawrence Perlman        Chairman of the Board, Chief Executive
-----------------------     Officer and Director (principal executive officer)
Lawrence Perlman


/s/ John R. Eickhoff        Executive Vice President and Chief
-----------------------     Financial Officer (principal financial officer)
John R. Eickhoff


/s/ Loren D. Gross          Vice President and Corporate Controller,
-----------------------     (principal accounting officer)
Loren D. Gross


                                  II-4

<PAGE>

SIGNATURES CONTINUED
--------------------




/s/ Bruce R. Bond            Director
-----------------------
Bruce R. Bond


/s/ Nicholas D. Chabraja     Director
-----------------------
Nicholas D. Chabraja


/s/ Ruth M. Davis            Director
-----------------------
Ruth M. Davis


/s/ Robert H. Ewald          Director
-----------------------
Robert H. Ewald


/s/ Richard G. Lareau        Director
-----------------------
Richard G. Lareau


/s/ Ronald T. LeMay          Director
-----------------------
Ronald T. LeMay


/s/ George R. Lewis          Director
-----------------------
George R. Lewis


/s/ Ronald L. Turner         President, Chief Operating Officer
-----------------------      and Director
Ronald L. Turner


/s/ Carole J. Uhrich         Director
-----------------------
Carole J. Uhrich


/s/ Paul S. Walsh            Director
-----------------------
Paul S. Walsh
</TABLE>

                                II-5

<PAGE>

                                  EXHIBIT INDEX

<TABLE>
<CAPTION>
Exhibit                                                  Page
-------                                                  ----
<C>      <S>                                     <S>
5.01     Opinion of William E. McDonald          Filed electronically herewith

23.01    Consent of KPMG LLP                     Filed electronically herewith

23.02    Consent of Grant Thornton LLP           Filed electronically herewith

23.03    Consent of William E. McDonald.         Included in Exhibit 5.01

24.01    Power of Attorney.                      Included on page II-4 of this
                                                 Registration Statement
</TABLE>
[{"type": "S-8", "sequence": "1", "description": "S-8", "secsgml_size_bytes": 20086}]
{"company-data": {"conformed-name": "CERIDIAN CORP", "cik": "0000109758", "assigned-sic": "3571", "irs-number": "520278528", "state-of-incorporation": "DE", "fiscal-year-end": "1231"}, "filing-values": {"form-type": "S-8", "act": "33", "file-number": "333-89565", "film-number": "99732503"}, "business-address": {"street1": "8100 34TH AVE S", "city": "MINNEAPOLIS", "state": "MN", "zip": "55425", "phone": "6128538100"}, "former-company": [{"former-conformed-name": "CONTROL DATA CORP /DE/", "date-changed": "19920703"}, {"former-conformed-name": "COMMERCIAL CREDIT CO", "date-changed": "19680910"}]}
As filed with the Securities and Exchange Commission on October 22, 1999
                                                     Registration No. 333-______

--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

                       SECURITIES AND EXCHANGE COMMISSION
                              Washington, DC 20549
                               ------------------

                                    FORM S-8
                             REGISTRATION STATEMENT
                        Under The Securities Act of 1933
                               ------------------

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

                   DELAWARE                            52-0278528
         (State or other jurisdiction               (I.R.S. Employer
       of incorporation or organization)           Identification No.)

            8100 34th Avenue South                        55425
            Minneapolis, Minnesota                     (Zip Code)
   (Address of principal executive offices)

                 CERIDIAN CORPORATION 1999 STOCK INCENTIVE PLAN
                            (Full title of the plan)

                               William E. McDonald
                 Associate General Counsel and Deputy Secretary
                              Ceridian Corporation
                             8100 34th Avenue South
                          Minneapolis, Minnesota 55425
                     (Name and address of agent for service)

                                 (612) 853-8100
          (Telephone number, including area code, of agent for service)

                       CALCULATION OF REGISTRATION FEE (1)
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
                                             Proposed                Proposed
  Title of                                   maximum                 maximum
securities             Amount to             offering                aggregate              Amount of
     to be                 be                price per               offering              registration
registered           Registered (2)          share                   price                     fee
---------------------------------------------------------------------------------------------------------
Common Stock
($.50 par value)     3,264,000 shares             $19.9375 (3)        $ 65,076,000        $     18,092
                         7,000 shares               $27.00 (3)        $    189,000        $         53
                        20,500 shares               $28.50 (3)        $    584,250        $        163
                       142,500 shares               $30.75 (3)        $  4,381,875        $      1,219
                        14,500 shares             $32.1825 (3)        $    466,646        $        130
                         3,500 shares             $31.3125 (3)        $    109,594        $         31
                        10,000 shares             $32.5625 (3)        $    325,625        $         91
                     6,538,000 shares              $17.875 (4)        $116,866,750        $     32,489
                    -----------------                                 ------------        ------------
         Total      10,000,000 shares                                 $187,999,740        $     52,268
---------------------------------------------------------------------------------------------------------
---------------------------------------------------------------------------------------------------------
(1)    This Registration Statement is also deemed, pursuant to Instruction E to
       Form S-8, to relate to 2,457,462 shares of the 3,000,000 shares that had
       been previously registered on Form S-8 (File No. 333-28069) in connection
       with a predecessor plan, with respect to which a fee of $32,446 has been
       previously paid.
(2)    In addition, pursuant to Rule 416(a) under the Securities Act of 1933, as
       amended (the "Act"), this Registration Statement also covers an
       indeterminate number of additional shares that may be offered or issued
       as a result of the anti-dilution provisions of the above-referenced plan.
(3)    Calculated pursuant to Rule 457(h) for the purpose of calculating the
       registration fee, based upon the price at which outstanding options may
       be exercised.
(4)    Estimated solely for the purpose of calculating the registration fee in
       accordance with Rule 457(h)(1) and (c), based upon the average of the
       reported high and low prices of the Common Stock as reported on the
       Consolidated Transaction Reporting System of the New York Stock Exchange
       on October 19, 1999.
EXPLANATORY NOTE

         On May 30, 1997, a total of 3,000,000 shares of Common Stock of
Ceridian Corporation (the "Company") to be issued in connection with the
Company's 1993 Long-Term Incentive Plan (Amended and Restated on May 14, 1997)
(the "1993 Plan"), were registered with the Securities and Exchange Commission
(the "Commission") by a Registration Statement on Form S-8 (File No. 333-28069).
On May 20, 1999, the stockholders of the Company approved the 1999 Stock
Incentive Plan (the "1999 Plan"), which replaces the 1993 Plan. Both the 1999
Plan and the 1993 Plan are long term incentive plans. As of October 4, 1999, two
million four hundred fifty seven thousand four hundred sixty two (2,457,462)
shares of such registered shares of Common Stock of the Company under the 1993
Plan had not been issued under the 1993 Plan and, pursuant to Instruction E to
Form S-8 and the telephonic interpretation of the Commission pertaining to "Form
S-8"setforth in the Division of Corporation Finance's Manual of
Publicly-Available Telephone Interpretations (July 1997), are carried forward
to, and deemed covered by this Registration Statement on Form S-8 in connection
with the 1999 Plan.

                                    PART II.

               INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

Item 3.    INCORPORATION OF DOCUMENTS BY REFERENCE.

         The following documents, which have been filed by Ceridian Corporation
(the "Company") with the Securities and Exchange Commission, are incorporated by
reference in this Registration Statement, as of their respective dates:

(a)      The Company's Annual Report on Form 10-K for the fiscal year ended
         December 31, 1998;

(b)      The Company's Quarterly Report on Form 10-Q for the quarters ending
         March 31, 1999 and June 30, 1999;

(c)      The Company's Current Report on Form 8-K as filed with the Securities
         and Exchange Commission on June 21, 1999, as amended and filed on
         August 20, 1999;

(d)      All other reports filed by the Company pursuant to Sections 13(a) or
         15(d) of the Securities Exchange Act of 1934, as amended (the "Exchange
         Act") since December 31, 1998; and

(e)      The description of the Company's capital stock contained in the
         Company's Registration Statement on Form S-4 (File No. 33-64089),
         including any amendments or reports filed for the purpose of updating
         such description.

         All documents filed by the Company pursuant to Sections 13(a), 13(c),
14 and 15(d) of the Exchange Act, subsequent to the date hereof and prior to the
filing of a post-effective amendment which indicates that all securities offered
hereby have been sold or which deregisters all securities remaining unsold,
shall be deemed to be incorporated by reference herein and to be a part hereof
from the respective dates of filing of such documents.

                                       II-1
Item 4.  DESCRIPTION OF SECURITIES.

         The Company's Common Stock is registered under Section 12 of the
Exchange Act.

Item 5.  INTERESTS OF NAMED EXPERTS AND COUNSEL.

         William E. McDonald, Associate General Counsel and Deputy Secretary for
the Company, has provided an opinion as to the legality of the securities being
registered hereby. As a result of awards under stock-based compensation plans
maintained by the Company, including the Employee Stock Purchase Plan, Mr.
McDonald holds options to acquire shares of common stock of the Company with a
value that may exceed $50,000 upon vesting.

Item 6.  INDEMNIFICATION OF DIRECTORS AND OFFICERS.

         Section 145 of the Delaware General Corporation Law of the State of
Delaware ("DGCL") grants each corporation organized thereunder, such as the
Company, the power to indemnify its directors and officers against liability for
certain of their acts. Section 102(b)(7) of the DGCL permits a provision in the
certificate of incorporation of each corporation organized thereunder
eliminating or limiting, with certain exceptions, the personal liability of a
director to the corporation or its stockholders for monetary damages for breach
of fiduciary duty as a director. The Company's certificate of incorporation
contains such a provision. The foregoing statements are subject to the detailed
provisions of Sections 145 and 102(b)(7) of the DGCL.

         Article VI of the Company's Bylaws provides that the Company shall
indemnify its officers, directors and employees to the fullest extent permitted
by the DGCL in connection with proceedings with which any such person is
involved by virtue of his or her status as an officer, director or employee. The
Company has also by contract agreed to indemnify its directors against damages,
judgments, settlements and costs arising out of any actions against the
directors brought by reason of the fact that they are or were directors. The
Company maintains directors' and officers' liability insurance, including a
reimbursement policy in favor of the Company.

Item 7.  EXEMPTION FROM REGISTRATION CLAIMED.

         Not applicable.

Item 8.  EXHIBITS.

         The following is a complete list of Exhibits filed or incorporated by
reference as part of this registration statement:
Exhibit:    Description:
         --------    ------------
5.01        Opinion and consent of William E. McDonald.

         23.01       Consent of KPMG LLP.

         23.02       Consent of Grant Thornton LLP.

         23.03       Consent of William E. McDonald (included in Exhibit 5.01).

         24.01       Power of Attorney (included on page II-4 of the
                     Registration Statement).
Item 9   UNDERTAKINGS.

A.       The undersigned registrant hereby undertakes:

                                       II-2
(1)      To file, during any period in which offers or sales are being
made, a post-effective amendment to this registration statement:

                  (i)      To include any prospectus required by Section
                           10(a)(3) of the Securities Act of 1933;

                  (ii)     To reflect in the prospectus any facts or events
                           arising after the effective date of the registration
                           statement (or the most recent post-effective
                           amendment thereof) which, individually or in the
                           aggregate, represent a fundamental change in the
                           information set forth in the registration statement.
                           Notwithstanding the foregoing, any increase or
                           decrease in volume of securities offered (if the
                           total dollar value of securities would not exceed
                           that which was registered) and any deviation from the
                           low or high end of the estimated maximum offering
                           range may be reflected in the form of prospectus
                           filed with the Securities and Exchange Commission
                           pursuant to Rule 424(b) if, in the aggregate, the
                           changes in volume and price represent no more than a
                           20% change in the maximum aggregate offering price
                           set forth in the "Calculation of Registration Fee"
                           table in the effective Registration Statement;

                  (iii)    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;

PROVIDED, HOWEVER, that paragraphs A(1)(i) and A(1)(ii) above will not apply if
the information required to be included in a post-effective amendment by those
paragraphs is contained in periodic reports filed by the registrant pursuant to
Section 13 or Section 15(d) of the Securities Exchange Act of 1934 that are
incorporated by reference in the registration statement.

         (2)      That, for the purpose 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 to be 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 Section 15(d) of the
Exchange Act 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 the foregoing provisions, 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
Securities Act of 1933 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 other
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, unless
in the opinion of its counsel the matter has been settled by controlling
precedent, submit to a court of appropriate jurisdiction the question whether
such indemnification by it is against public policy as expressed in the
Securities Act of 1933 and will be governed by the final adjudication of such
issue.

                                       II-3
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 Minneapolis, State of Minnesota, on the 22nd day of
October, 1999.

                               CERIDIAN CORPORATION

                               By:  /s/ Lawrence Perlman
                                    --------------------------------
                                    Lawrence Perlman
                                    Chairman of the Board and
                                    Chief Executive Officer

                                POWER OF ATTORNEY

         Each person whose signature appears below constitutes and appoints
Lawrence Perlman, John R. Eickhoff and Gary M. Nelson, and each of them, his or
her true and lawful attorney-in-fact and agent with full powers of substitution
and resubstitution, for and in his or her name, place and stead, in any and all
capacities, to sign any or all amendments (including post-effective amendments)
to this registration statement, and to file the same, with all exhibits thereto,
and other documents in connection therewith, with the Securities and Exchange
Commission, granting unto said attorney-in-fact and agent full power and
authority to do and perform each and every act and thing requisite or necessary
to be done in and about the premises, as fully to all intents and purposes as he
or she might or could do in person, hereby ratifying and confirming all that
said attorney-in-fact and agent or his substitute or substitutes, may lawfully
do or cause to be done by virtue thereof.

         Pursuant to the requirements of the Securities Act of 1933, this
Registration Statement has been signed by the following persons in the
capacities indicated on the 22nd day of October, 1999.
Signature                                Title
    ---------                                -----
/s/ Lawrence Perlman        Chairman of the Board, Chief Executive
-----------------------     Officer and Director (principal executive officer)
Lawrence Perlman

/s/ John R. Eickhoff        Executive Vice President and Chief
-----------------------     Financial Officer (principal financial officer)
John R. Eickhoff

/s/ Loren D. Gross          Vice President and Corporate Controller,
-----------------------     (principal accounting officer)
Loren D. Gross

                                  II-4
SIGNATURES CONTINUED
--------------------

/s/ Bruce R. Bond            Director
-----------------------
Bruce R. Bond

/s/ Nicholas D. Chabraja     Director
-----------------------
Nicholas D. Chabraja

/s/ Ruth M. Davis            Director
-----------------------
Ruth M. Davis

/s/ Robert H. Ewald          Director
-----------------------
Robert H. Ewald

/s/ Richard G. Lareau        Director
-----------------------
Richard G. Lareau

/s/ Ronald T. LeMay          Director
-----------------------
Ronald T. LeMay

/s/ George R. Lewis          Director
-----------------------
George R. Lewis

/s/ Ronald L. Turner         President, Chief Operating Officer
-----------------------      and Director
Ronald L. Turner

/s/ Carole J. Uhrich         Director
-----------------------
Carole J. Uhrich

/s/ Paul S. Walsh            Director
-----------------------
Paul S. Walsh
II-5
EXHIBIT INDEX
Exhibit                                                  Page
-------                                                  ----
5.01     Opinion of William E. McDonald          Filed electronically herewith

23.01    Consent of KPMG LLP                     Filed electronically herewith

23.02    Consent of Grant Thornton LLP           Filed electronically herewith

23.03    Consent of William E. McDonald.         Included in Exhibit 5.01

24.01    Power of Attorney.                      Included on page II-4 of this
                                                 Registration Statement