<ARTICLE> 5
<LEGEND>
THIS SCHEDULE CONTAINS SUMMARY FINANCIAL INFORMATION EXTRACTED FROM THE MAY
31, 1998 CONSOLIDATED FINANCIAL STATEMENTS AND RELATED NOTES TO CONSOLIDATED
FINANCIAL STATEMENTS OF PAYCHEX, INC., AND IS QUALIFIED IN ITS ENTIRETY BY
REFERENCE TO SUCH FINANCIAL STATEMENTS.  THIS SCHEDULE INCLUDES RESTATED
AMOUNTS FOR THE YEARS ENDED MAY 31, 1997 AND 1996 FOR EARNINGS PER SHARE,
RELATED TO THE ADOPTION OF STATEMENT OF FINANCIAL ACCOUNITNG STANDARDS NO.
128, "EARNINGS PER SHARE", EFFECTIVE FOR PERIODS ENDING AFTER DECEMBER 15,
1997.  IN ADDITION, ON MAY 22, 1998, PAYCHEX, INC., DISTRIBUTED A
THREE-FOR-TWO STOCK SPLIT EFFECTED IN THE FORM OF A 50% STOCK DIVIDEND TO
STOCKHOLDERS OF RECORD AS OF MAY 8, 1998.  THEREFORE, ALL APPLICABLE AMOUNTS
INCLUDED IN THIS SCHEDULE AFFECTED BY THE STOCK SPLIT HAVE BEEN ADJUSTED.
</LEGEND>
<RESTATED>
<CIK> 0000723531
<NAME> PAYCHEX, INC.
<MULTIPLIER> 1,000
       
                                                                     
<PERIOD-TYPE>                   YEAR                   YEAR                   YEAR
<FISCAL-YEAR-END>                          MAY-31-1998             MAY-31-1997             MAY-31-1996
<PERIOD-START>                             JUN-01-1997             JUN-01-1996             JUN-01-1995
<PERIOD-END>                               MAY-31-1998             MAY-31-1997             MAY-31-1996
<CASH>                                          35,571                  50,213                  19,999
<SECURITIES>                                 1,369,468<F1>           1,029,413<F1>             702,442<F1>
<RECEIVABLES>                                   67,823                  55,989                  49,461
<ALLOWANCES>                                         0                       0                       0
<INVENTORY>                                          0                       0                       0
<CURRENT-ASSETS>                             1,478,778               1,140,661                 775,985
<PP&E>                                         152,051                 126,267                 111,010
<DEPRECIATION>                                  87,353                  72,089                  60,355
<TOTAL-ASSETS>                               1,549,787               1,201,323                 831,585
<CURRENT-LIABILITIES>                        1,215,660                 946,047                 637,346
<BONDS>                                              0                       0                       0
<PREFERRED-MANDATORY>                                0                       0                       0
<PREFERRED>                                          0                       0                       0
<COMMON>                                         1,632                   1,085                     716
<OTHER-SE>                                     327,975                 250,457                 190,356
<TOTAL-LIABILITY-AND-EQUITY>                 1,549,787               1,201,323                 831,585
<SALES>                                              0                       0                       0
<TOTAL-REVENUES>                               993,445                 734,699                 566,443
<CGS>                                                0                       0                       0
<TOTAL-COSTS>                                  631,472                 450,000                 334,370
<OTHER-EXPENSES>                                     0                       0                       0
<LOSS-PROVISION>                                     0                       0                       0
<INTEREST-EXPENSE>                                   0                       0                       0
<INCOME-PRETAX>                                144,173                 103,656                  75,389
<INCOME-TAX>                                    41,954                  28,506                  20,354
<INCOME-CONTINUING>                            102,219                  75,150                  55,035
<DISCONTINUED>                                       0                       0                       0
<EXTRAORDINARY>                                      0                       0                       0
<CHANGES>                                            0                       0                       0
<NET-INCOME>                                   102,219                  75,150                  55,035
<EPS-PRIMARY>                                      .63                     .46                     .34
<EPS-DILUTED>                                      .62                     .46                     .34
<FN>
<F1>SECURITIES - Includes amounts related to Electronic Network Servics
investments with a balance at May 31, 1998, 1997, and 1996 of $1,154,501,
$896,633, and $599,475, respectively.

</FN>