Table of Contents

INFORMATION REQUIRED IN PROXY STATEMENT

PROXY STATEMENT PURSUANT TO SECTION 14(a) OF THE SECURITIES

Filed by the Registrant þ

Filed by a Party other than the Registrant o

Check the appropriate box:

PAYCHEX, INC.

Payment of Filing Fee (Check the appropriate box):

þ	No fee required.
o	Fee computed on table below per Exchange Act Rules 14a-6(i)(1) and 0-11.

(1)	Title of each class of securities to which transaction applies:

(2)	Aggregate number of securities to which transaction applies:

(3)	Per unit price or other underlying value of transaction computed pursuant to Exchange Act Rule 0-11 (set forth the amount on which the filing fee is calculated and state how it was determined):

(4)	Proposed maximum aggregate value of transaction:

(5)	Total fee paid:

o	Fee paid previously with preliminary materials.
o	Check box if any part of the fee is offset as provided by Exchange Act Rule 0-11(a)(2) and identify the filing for which the offsetting fee was paid previously. Identify the previous filing by registration statement number, or the Form or Schedule and the date of its filing.

(1)	Amount Previously Paid:

(2)	Form, Schedule or Registration Statement No.:

(3)	Filing Party:

(4)	Date Filed:

Table of Contents

August 31, 2004

Dear Paychex Stockholder:

      The Board of Directors cordially invites you to attend our Annual Meeting of Stockholders (the “Annual Meeting”) on Wednesday, October 6, 2004 at 10:00 a.m. at the Rochester Riverside Convention Center, 123 East Main Street, Rochester, New York.

      This booklet includes the formal Notice of Annual Meeting of Stockholders and the Proxy Statement. The Proxy Statement tells you about the agenda items and the procedures for the Annual Meeting. It also provides certain information about the Company, its Board of Directors, and its executive officers.

      It is important that your shares be represented at the Annual Meeting. Whether or not you plan to attend the Annual Meeting, you are encouraged to vote. You may vote by Internet, telephone, written proxy, or written ballot at the Annual Meeting. We encourage you to use the Internet because it is the most cost-effective way to vote.

      We hope you will be able to attend the Annual Meeting and would like to take this opportunity to remind you that your vote is important. If you need special assistance at the Annual Meeting, please contact the Secretary of the Company at (585) 385-6666, or write to Paychex, Inc., c/o Secretary, 911 Panorama Trail South, Rochester, New York 14625-2396.

	Sincerely,
	B. Thomas Golisano
	Chairman, President, and
	Chief Executive Officer

Table of Contents

PAYCHEX, INC.

911 Panorama Trail South • Rochester, New York 14625-2396

NOTICE OF ANNUAL MEETING OF STOCKHOLDERS

Table of Contents

PROXY STATEMENT

ANNUAL MEETING OF STOCKHOLDERS OF PAYCHEX, INC.

       This Proxy Statement is first being sent or given to stockholders of Paychex, Inc. (“Paychex” or the “Company”) beginning on or about August 31, 2004, in connection with the solicitation of proxies by the Board of Directors (the “Board”) to be voted at the 2004 Annual Meeting of Stockholders (the “Annual Meeting”). The Annual Meeting will be held on October 6, 2004 at 10:00 a.m. at the Rochester Riverside Convention Center, 123 East Main Street, Rochester, New York.

Stockholders Entitled to Vote

      The Board has fixed the close of business on August 9, 2004, as the record date for determining the holders of common stock entitled to notice of, and to vote at, the Annual Meeting. Stockholders will be entitled to one vote for each share of common stock held as of the record date.

How to Vote

      Your vote is very important and we hope that you will attend the Annual Meeting. However, whether or not you plan to attend the Annual Meeting, please vote by proxy in accordance with the instructions on your proxy card, voting instruction form (from your bank or broker), or that you received through electronic mail. There are three convenient ways of submitting your vote:

	•	Voting by Internet – You can vote via the Internet by visiting the Web site noted on your proxy card. Internet voting is available 24 hours a day. We encourage you to vote via the Internet, as it is the most cost-effective way to vote.
	•	Voting by telephone – You can also vote your shares by telephone by calling the toll-free telephone number indicated on your proxy card and following the voice prompt instructions. Telephone voting is available 24 hours a day.
	•	Voting by mail – If you choose to vote by mail, simply mark your proxy card, date and sign it, and return it in the postage-paid envelope provided.

      The deadline for Internet or telephone voting is 11:59 p.m. Eastern Time on October 4, 2004. If you vote by telephone or the Internet, you do not need to return your proxy card. Signing and returning your proxy card or submitting your proxy via the Internet or by telephone does not affect your right to vote in person if you attend the Annual Meeting and your shares are registered in your name. If your shares are held in the name of a bank, broker, or other holder of record, you must obtain a proxy, executed in your favor, from the holder of record to be able to vote at the Annual Meeting.

Revoking Your Proxy

      You can revoke your proxy at any time prior to it being voted at the Annual Meeting by either:

	•	Providing written notice of revocation to the Secretary of the Company;
	•	Submitting a later-dated proxy via the Internet, telephone, or mail; or
	•	Voting in person at the Annual Meeting.

General Information on Voting

      The Company had outstanding on August 9, 2004, the record date, 378,180,769 shares of common stock, each of which entitles the holder to one vote. A majority of the outstanding shares (189,090,386 shares) present at the Annual Meeting in person or by proxy will constitute a quorum.

      All votes properly cast and not revoked will be voted at the Annual Meeting in accordance with the stockholder’s directions. Shares voted by proxy card received without choices specified will be voted FOR the seven nominees for election to the Board of Directors of the Company.

1

Table of Contents

      A plurality of votes cast is required for the election of Directors, meaning the nominees receiving the most votes will be elected. Only votes cast for nominees will be counted. You may choose to vote for a nominee or withhold your vote. Votes that are withheld will be excluded entirely from the vote and will have no effect on the outcome of the vote. A broker non-vote will have no effect on the outcome of the election of Directors.

Voting by Participants in the Paychex Employee Stock Ownership Plan Stock Fund

      If a stockholder is a participant in the Paychex Employee Stock Ownership Plan Stock Fund (ESOP) of the Paychex, Inc. 401(k) Incentive Retirement Plan, the proxy card also will serve as a voting instruction for the Trustee of the ESOP, where all accounts are registered in the same name. If shares of common stock in the ESOP are not voted, those shares will be voted by the Trustee in the same proportions as the shares properly voted by other participants in the ESOP. Voting by ESOP participants will close at 11:59 p.m. Eastern Time on October 2, 2004. The Trustee will then vote shares of common stock in the ESOP not voted by the participants by the established deadline.

Cost of Solicitation of Proxies

      The Company will pay the cost of solicitation of proxies. The Company will reimburse any banks, brokers and other custodians, nominees, and fiduciaries for their expenses in forwarding proxies and proxy solicitation material to the beneficial owners of the shares held by them.

Delivery of Proxy Materials and Annual Report

      The Notice of Annual Meeting of Stockholders, Proxy Statement, Proxy Card, and 2004 Annual Report are being mailed to stockholders on or about August 31, 2004. You may also obtain a copy of the Company’s Annual Report on Form 10-K filed with the Securities and Exchange Commission, without charge, upon written request submitted to Paychex, Inc., c/o Secretary, 911 Panorama Trail South, Rochester, New York 14625-2396.

      Under U.S. Securities and Exchange Commission (SEC) rules, a single set of Annual Reports and Proxy Statements may be sent to any household at which two or more stockholders reside, if they appear to be members of the same family, unless otherwise requested. This procedure, called “householding”, allows the Company to reduce printing and mailing expenses of delivering duplicate disclosure materials to stockholders who may have more than one stock account or who share an address with another Paychex stockholder. Stockholders who participate in householding will continue to receive separate proxy cards.

      If you are a registered stockholder (owning your stock directly and not through a bank or broker) who shares an address with another stockholder of record, you may be eligible for householding for future mailings. If you wish to affirmatively consent to participate in householding, please indicate “Yes” in the householding election on your proxy card. If you wish to continue to receive separate annual reports and proxy statements for each account in your household, you must withhold your consent to householding by indicating “No” in the householding election on your proxy card. If you do not respond, your consent will be implied, and householding of future mailings will start sixty days after the mailing of this Proxy Statement. Affirmative or implied consent will be perpetual unless you withhold it or revoke it.

      You may revoke your consent at any time by calling toll-free (800) 542-1061. If you revoke your consent, you will be removed from the householding program within thirty days of receipt of your revocation, and each stockholder at your address will receive individual copies of our disclosure documents.

      If you own Paychex stock beneficially through a bank or broker, you may already be subject to householding if you meet the criteria. If you wish to receive a separate Annual Report and Proxy Statement in future mailings, you should contact your bank or broker.

      The Notice of Annual Meeting of Stockholders, Proxy Statement, and 2004 Annual Report are also available on the Company’s Web site at www.paychex.com. Instead of receiving paper copies of the Annual Report and Proxy Statement in the mail, stockholders can elect to receive an e-mail message, which will provide a link to these documents on the Internet. Opting to receive your proxy materials online saves the Company the cost of producing and mailing bulky documents. To give your consent to receive future documents via electronic delivery, please vote your proxy via the Internet and follow the instructions to register for electronic delivery.

2

Table of Contents

PROPOSAL 1 • ELECTION OF DIRECTORS FOR A ONE-YEAR TERM

      Stockholders annually elect Directors to serve for one year and until their successors have been elected and shall have qualified. The Board of Directors has nominated for election to the Board of Directors the seven persons listed below, each of whom currently serves as a Director. Four of the seven nominees are neither employees nor former employees of the Company. If elected, each nominee will hold office until the Annual Meeting to be held in 2005, and until their successor is elected and has qualified.

      Although the Board of Directors believes that all of the nominees will be available to serve, the proxies may exercise discretionary authority to vote for substitutes proposed by the Board of Directors of the Company.

      Biographies are provided below setting forth certain information with respect to the nominees for election as Directors of the Company, none of whom is related to any other nominee or executive officer.

3

Table of Contents

      The Board of Directors recommends the election of each of the nominees identified above and, unless otherwise directed, the proxies named will vote the proxy FOR the election of these nominees.

Retiring Director

      Betsy S. Atkins, a member of the Board of Directors since 2001, has declined to stand for re-election to the Board of Directors.

4

Table of Contents

CORPORATE GOVERNANCE

Board Meetings

      The Board of Directors of the Company (the “Board”) met five times during the fiscal year ended May 31, 2004 (“fiscal 2004”). To the extent practicable, Directors are expected to attend Board meetings and meetings of the Committees on which they serve. Each Director attended more than 75% of all meetings of the Board of Directors and of the Committees on which such Director served during fiscal 2004. Directors are encouraged to attend annual meetings of stockholders. Last year, seven Directors attended the Annual Meeting.

      In fiscal 2004, non-employee Directors were paid $12,000 annually plus $1,250 for each Board meeting attended and $750 for each Committee meeting attended. The Chairman of the Audit Committee, currently Mr. Flaschen, was paid an additional $750 for each meeting chaired. In July 2004, the compensation for non-employee Directors was increased to $25,000 annually plus $2,500 for each Board meeting attended and $1,000 for each Committee meeting attended. The Chairman of the Audit Committee is paid an additional $1,000 for each meeting chaired. In July 2003, each non-employee director was awarded a stock option grant under the Paychex, Inc. 2002 Stock Incentive Plan for 10,000 shares of common stock at an exercise price of $29.55 per share, which expires in July 2013. The exercise price of these stock options is equal to the market price of the underlying stock on the date of the grant.

      The Board has determined that each of the Directors, other than Mr. Golisano, is independent within the meaning of applicable Securities and Exchange Commission (SEC) and The NASDAQ Stock Market® (NASDAQ) director independence standards.

Executive Sessions

      Regularly scheduled executive sessions of the independent members of the Board of Directors without members of management are held in conjunction with meetings of the Board. The Board has selected Mr. Tucci to preside at all executive sessions of the independent Directors.

Board Committees

      During fiscal 2004, the Board had the following four standing committees:

      The Executive Committee, which is comprised of Mr. Golisano (Chairman), Mr. Clark, and Mr. Horsley, may exercise all the powers and authority of the Board of Directors except as limited by law. The Executive Committee held one meeting during fiscal 2004.

      The Audit Committee is comprised of Ms. Atkins, Mr. Clark, Mr. Flaschen (Chairman), and Mr. Inman. The Board has determined that all members of the Audit Committee meet the independence, experience, and other applicable NASDAQ listing requirements, and that Mr. Flaschen qualifies as an “Audit Committee Financial Expert,” as defined by applicable rules. The Audit Committee’s responsibilities are described in the Audit Committee Charter adopted by the Board, which is attached as Appendix A to this Proxy Statement. The Audit Committee held six meetings during fiscal 2004.

      The Compensation Committee was comprised of Mr. Flaschen, Mr. Horsley, Mr. Inman, and Mr. Tucci (Chairman). The Compensation Committee’s responsibilities were as described in the Compensation Committee Charter adopted by the Board, which is attached as Appendix B to this Proxy Statement. The Compensation Committee held two meetings during fiscal 2004.

      The Investment Committee is comprised of Mr. Clark, Mr. Horsley, and Mr. Inman (Chairman). The Investment Committee’s responsibilities are described in the Investment Committee Charter adopted by the Board, which is attached as Appendix C to this Proxy Statement. The Investment Committee held one meeting during fiscal 2004.

      In July 2004, the Board of Directors created a new Governance and Compensation Committee comprised of Mr. Tucci (Chairman), Mr. Flaschen, Mr. Horsley, and Mr. Inman. The Board has determined that all members of the Governance and Compensation Committee meet the NASDAQ independence criteria. The Governance and

5

Table of Contents

Nomination Process

      The Company has a standing Governance and Compensation Committee, which performs the function of a nominating committee. The Board has determined that it is necessary for the continued success of the Company to ensure that the Board is composed of individuals having a variety of complementary experience, education, training, and relationships relevant to the then-current needs of the Board and the Company. The Nomination Policy included in the Governance and Compensation Committee Charter is intended to achieve this result.

      In evaluating candidates for nomination to the Board, the Nomination Policy requires Governance and Compensation Committee members to consider the contribution that a candidate for nomination would be expected to make to the Board and the Company, based upon the current composition and needs of the Board, and the candidate’s demonstrated business judgment, leadership abilities, integrity, prior experience, education, training, relationships, and other factors that the Board determines relevant. In identifying candidates for nomination to fill vacancies created by the expiration of the term of any incumbent Director, the Nomination Policy requires Governance and Compensation Committee members to determine whether such incumbent Director is willing to stand for re-election and, if so, to take into consideration the value to the Board and to the Company of continuity and familiarity with the Company’s business. The Board has previously used a third party search firm to identify Director candidates and the Nomination Policy authorizes the Governance and Compensation Committee to continue this practice.

      The Nomination Policy requires the Governance and Compensation Committee to consider candidates for nomination to the Board recommended by any reasonable source, including stockholders. Stockholders who wish to do so may recommend candidates for nomination by identifying such candidates in written communications to the chairperson of the Governance and Compensation Committee in accordance with the policy described below in the Section entitled “Communications with the Board of Directors.”

Communications with the Board of Directors

      The Board has an adopted policy that permits stockholders to communicate in writing with the Board and with chairpersons of standing committees of the Board by mailing their communications to the Company Secretary. Such communications must be clearly marked “Shareholder — Board Communication,” and in the case of communications intended for committee chairpersons, must identify the committee. Any such communications that do not identify a standing committee will be forwarded to the Board. The Company Secretary will forward such communications to the Board or to the appropriate standing committee of the Board, as the case may be.

CODE OF ETHICS

      The Company has adopted a Code of Ethics that applies to all of its Directors, officers, and employees. The Code of Ethics is available for review on the Company’s Web site at www.paychex.com at the Investor Relations section under “Corporate Governance.” The Company intends to disclose any amendment to, or waiver from, a provision of its Code of Ethics that relates to any element of the Code of Ethics definition enumerated in Item 406 of SEC Regulation S-K by posting such information on its Web site at the address specified above.

6

Table of Contents

REPORT OF THE AUDIT COMMITTEE

      The Audit Committee of the Board of Directors oversees the Company’s financial reporting process on behalf of the Board of Directors. Management has the primary responsibility for the financial statements and the reporting process, including the systems of internal controls. In fulfilling its oversight responsibilities, the Audit Committee reviewed the audited financial statements in the Fiscal Year 2004 Annual Report on Form 10-K with management including a discussion of the quality, not just the acceptability, of the accounting principles, the reasonableness of significant judgments, and the clarity of disclosures in the financial statements.

      The Company’s independent registered public accounting firm, Ernst & Young LLP, is responsible for expressing an opinion on the conformity of the audited financial statements with the standards of the Public Company Accounting Oversight Board (United States). The Audit Committee reviewed with the independent auditors their judgments as to the quality, not just the acceptability, of the Company’s accounting principles and such other matters as are required to be discussed with the Audit Committee under Generally Accepted Auditing Standards. The Committee discussed with the independent auditors the matters required to be discussed by Statement on Auditing Standards No. 61, as amended by Statement on Auditing Standard No. 90 (Communications With Audit Committees). In addition, the Audit Committee has discussed with the independent auditors the auditors’ independence from management and the Company, including the matters in the written disclosures required by the Independence Standards Board Standard No. 1 (Independence Discussions with Audit Committees). The Audit Committee has also considered whether the independent auditor’s provision of other non-audit services to the Company is compatible with the auditor’s independence. The Audit Committee held six meetings during fiscal 2004.

      The Audit Committee discussed with the Company’s internal auditors and independent auditors the overall scope and plans for their respective audits. The Audit Committee meets with the internal and independent auditors, with and without management present, to discuss the results of their examinations, their evaluations of the Company’s internal controls, and the overall quality of the Company’s financial reporting.

      In reliance on the reviews and discussions referred to above, the Audit Committee recommended and the Board of Directors approved that the audited financial statements be included in the Company’s Annual Report on Form 10-K for the year ended May 31, 2004 for filing with the Securities and Exchange Commission. The Audit Committee will recommend to the Board of Directors, which will approve, the selection of the Company’s independent auditors.

	The Audit Committee:
	David J. S. Flaschen, Chairman
	Betsy S. Atkins
	G. Thomas Clark
	Grant M. Inman

7

Table of Contents

REPORT OF THE COMPENSATION COMMITTEE

      The Compensation Committee of the Board of Directors is responsible for making recommendations with respect to officers’ salaries and grants of stock options to the Company’s employees. The Compensation Committee’s recommendations are presented to the Board for discussion and decision.

      The compensation for executive officers is designed to be competitive with companies of similar size and performance, reward exceptional individual performance, tie compensation to overall Company objectives, and align the interest of executive officers with the interests of the stockholders. The components of the compensation program are base salary, annual incentive bonus, and stock option awards under the Company’s Stock Incentive Plan.

Base Salary and Annual Incentive Plan (Bonus)

      Annual compensation is composed primarily of base salary and an annual incentive bonus. The salaries of the executive officers are determined based on their performance and comparisons with base salaries paid to executive officers having similar responsibilities in comparable companies. The Compensation Committee and the Board have instituted an Officer Incentive Program, which provides for the executive officers the opportunity for annual cash bonuses of up to 50% of base salary based primarily on the Company’s annual revenue and operating income growth. The purpose of this bonus plan is to make a significant component of the executive officers’ annual compensation tied directly to overall Company financial performance.

Stock Incentive Plan

      The Company’s Stock Incentive Plan is designed to align executive officers’ compensation with long-term performance of the Company’s stock. Stock options are granted to executive officers, with the exception of Mr. Golisano, who receives no grants, in amounts based upon their individual performance. Stock options are granted at fair market value as of the date of the grant, and have a term of up to ten years. These options vest one-third each year commencing two years after the date of the grant. Stock options provide incentive for the executive officers to create stockholder value over the long term.

Compensation of Chief Executive Officer

      The Compensation Committee meets annually without the Chief Executive Officer to evaluate his performance and recommends to the Board the compensation to be paid to him. In performing that function, the Compensation Committee reviews the range and components of compensation paid to CEOs of other public companies. In particular, the Compensation Committee looks to those public companies whose size and performance are similar to those of Paychex, Inc.

      Mr. Golisano’s substantial stock position in the Company assures the Compensation Committee of his close identification with the interests of its stockholders. In view of his substantial stock position, Mr. Golisano has chosen not to receive any stock option grants. His compensation is reflective in part of the Compensation Committee’s evaluation of the Company’s performance in the areas of revenue, profitability, return on stockholders’ equity, and other areas. Salary adjustments reflect the Compensation Committee’s opinion of the impact, both short- and long-term, which Mr. Golisano’s creativity, strategic focus, and leadership had on these and other factors.

      Mr. Golisano’s fiscal 2004 compensation increased approximately 2% compared with his compensation for fiscal 2003. Mr. Golisano earned a bonus of approximately 39% of his base salary for fiscal 2004, compared with a bonus of approximately 40% of his base salary for fiscal 2003. Mr. Golisano’s bonus was determined based on the Officer Incentive Program described above. In fiscal 2004, Paychex achieved its fourteenth straight year of record revenues and net income. The Company’s total revenues increased 18% and net income increased 3% in fiscal 2004 over the prior year’s figures, while return on stockholders’ equity was 28%.

8

Table of Contents

Compensation of Other Executive Officers

      The Compensation Committee sets compensation for executive officers other than the CEO after the CEO provides the Compensation Committee with his evaluation of the performance of each executive officer and his recommendation with respect to base salary, bonus, and stock options. Compensation Committee members discuss his recommendations in light of their own experiences and familiarity with levels and components of compensation for persons with similar responsibilities in other public companies. The goal of the Compensation Committee is to compensate fairly for the job done, to reward extraordinary performance or promise, and to encourage long-term identification with stockholder interests through the award of stock options under the Company’s Stock Incentive Plan. Company performance is also considered.

Impact of Section 162(m) of the Internal Revenue Code

      Section 162(m) of the Internal Revenue Code generally limits the tax deductibility of annual compensation paid to certain executive officers to $1 million, unless specified requirements are met. The Compensation Committee has carefully considered the impact of this provision. At this time, it is the Compensation Committee’s intention to continue to compensate all executive officers based on overall performance. The Compensation Committee expects that most compensation paid to executive officers will qualify as a tax-deductible expense. For fiscal 2004, the Compensation Committee authorized compensation in excess of $1 million for Mr. Golisano. The Committee may in the future authorize compensation that is not deductible. The Stock Incentive Plan is designed to provide incentive compensation that will not count against the $1 million limitation.

	The Compensation Committee:
	Joseph M. Tucci, Chairman
	David J. S. Flaschen
	Phillip Horsley
	Grant M. Inman

Compensation Committee Interlocks and Insider Participation

      None of the members of the Compensation Committee were at any time during fiscal 2004, or at any other time, an officer or employee of the Company. During fiscal 2004, no member of the Committee or Board of Directors was an executive officer of another entity on whose compensation committee or board of directors an executive officer of Paychex served.

SECTION 16(a) BENEFICIAL OWNERSHIP REPORTING COMPLIANCE

      Section 16(a) of the Securities Exchange Act of 1934 requires Directors, officers, and beneficial owners of more than 10% of the Company’s common stock to file with the SEC reports of transactions in the stock. Based on information supplied to the Company and filings made with the SEC, the Company believes that during the fiscal year ended May 31, 2004, all Section 16(a) filing requirements applicable to its Directors, officers, and greater than ten percent beneficial owners were complied with, with the exception of one late filing for Mr. William Kuchta, an executive officer of the Company, covering a transaction involving 50 shares.

9

Table of Contents

EXECUTIVE OFFICER COMPENSATION

      The following table sets forth certain compensation information for the Company’s Chief Executive Officer and the Company’s four other most highly compensated executive officers.

SUMMARY COMPENSATION TABLE

(1)	The amounts reported in this column consist solely of the Company’s matching contributions under the Paychex, Inc. 401(k) Incentive Retirement Plan.
(2)	Mr. Mucci joined Paychex in March 2002 and was appointed an executive officer in October 2002.

10

Table of Contents

OPTION GRANTS IN LAST FISCAL YEAR

      The following table sets forth stock options granted in fiscal 2004 to the Company’s Chief Executive Officer and the Company’s four other most highly compensated executive officers. Under SEC regulations, companies are required to project an estimate of appreciation of the underlying shares of stock during the option term.

(1)	Non-qualified stock options were granted under the Paychex, Inc. 2002 Stock Incentive Plan. Options are granted at prices not less than 100% of the fair market value of the common stock at the date of the grant. The options granted are exercisable after two years in cumulative annual installments of 33 1/3% and expire after a term of ten years from the date of the grant.
(2)	In accordance with SEC rules, these columns show potential realizable values net of the option exercise price, but before any potential income taxes, assuming the market price of the Company’s common stock appreciates from the date of the grant over a period of ten years at the annualized rates of five and ten percent, respectively. However, the ultimate value will depend on the market value of the Company’s stock at a future date, which may or may not correspond to the projections above.

AGGREGATED OPTION EXERCISES IN LAST FISCAL YEAR AND

      The following table sets forth stock options exercised in fiscal 2004 by the Company’s Chief Executive Officer and the Company’s four other most highly compensated executive officers, and the number and value of all unexercised options at May 31, 2004. The value of “in-the-money” options refers to options having an exercise price that is less than the market price of the Company’s common stock at May 31, 2004.

(1)	Represents the market value of the Company’s common stock at the exercise date less the exercise price.
(2)	Represents the difference between the exercise price of the stock options and the $37.51 per share closing price of the Company’s common stock on May 28, 2004, for all in-the-money options held by each named executive officer. The in-the-money stock option exercise prices range from $3.14 per share to $29.55 per share. These stock options were granted at exercise prices equal to the fair market value of the stock on the date of the grant.

11

Table of Contents

BENEFICIAL OWNERSHIP OF PRINCIPAL STOCKHOLDERS,

      The following table sets forth information, based upon reports filed by such persons with the SEC, as of July 31, 2004, with respect to the beneficial ownership of common stock of the Company by (i) any person (including any “group” as that term is used in Section 13(d)(3) of the Exchange Act) who is known by the Company to be the beneficial owner of more than five percent (5%) of the Company’s voting securities, (ii) each Director and nominee for Director of the Company, (iii) each of the executive officers of the Company named in the Summary Compensation Table, and (iv) all Directors and executive officers of the Company as a group. Under the rules of the SEC, “beneficial ownership” is deemed to include shares for which the individual, directly or indirectly, has or shares voting or disposition power, whether or not they are held for the individual’s benefit.

**	Indicated percentage is less than 1%.

	(1)	Based upon the number of shares of common stock outstanding and deemed outstanding as of July 31, 2004, including shares that may be acquired within 60 days by exercise of options.
	(2)	Includes shares that may be acquired upon exercise of stock options, which are exercisable on or prior to September 29, 2004. The shares beneficially owned include: Ms. Atkins — 9,167 shares; Mr. Clark — 8,334 shares; Mr. Flaschen — 30,834 shares; Mr. Horsley — 8,334 shares; Mr. Inman — 8,334 shares; Mr. Sebo — 58,959 shares; Mr. Tucci — 30,834 shares; Mr. Turek — 175,012 shares; Mr. Morphy — 31,667 shares; Mr. Mucci — 5,000 shares; Ms. Rambo — 62,417 shares; and all Directors and executive officers as a group — 710,090 shares.
	(3)	Included in shares beneficially owned for Mr. Golisano and Mr. Clark are 646,068 shares owned by the B. Thomas Golisano Foundation for which Mr. Golisano and Mr. Clark are Trustees of a six-member Board of Trustees. Mr. Clark disclaims beneficial ownership of the 646,068 shares.
	(4)	Included in shares beneficially owned are the following number of shares held in the names of family members or other entities: Mr. Clark — 264,374 shares; Mr. Sebo — 17,780 shares; and Mr. Turek — 1,670 shares.

12

Table of Contents

INDEPENDENT PUBLIC ACCOUNTANTS

      The Company’s independent registered public accounting firm since 1983 has been Ernst & Young LLP. The Audit Committee expects to recommend that the Board of Directors reappoint this firm for fiscal year 2005. Representatives of Ernst & Young LLP are expected to be present at the Annual Meeting of Stockholders and to be available to respond to appropriate questions. They will also have the opportunity to make a statement if they desire to do so.

      The following table shows the aggregate fees for professional services rendered for the Company by Ernst & Young LLP for the fiscal years ended May 31, 2004 and 2003:

      Audit fees for the years ended May 31, 2004 and 2003, respectively, were for professional services rendered for the audit of the Company’s consolidated financial statements, and reviews of the financial statements included in the Company’s quarterly Form 10-Q’s.

      Audit related fees for the years ended May 31, 2004 and 2003, respectively, were for services associated with recent acquisitions, employee benefit plan audits, various statutory audits, and other reports.

      Tax fees for the years ended May 31, 2004 and 2003, respectively, were for services related to tax planning and compliance.

      The Audit Committee’s policy is to pre-approve all audit and permissible non-audit services provided by the independent accountants. The Audit Committee pre-approved all such audit and permissible non-audit services provided by the independent accountants during the year ended May 31, 2004.

13

Table of Contents

PERFORMANCE GRAPH

      The following graph shows a five-year comparison of the total cumulative returns of investing $100 on May 31, 1999, in Paychex, Inc. common stock, the S&P Data Processing and Outsourced Services (the “S&P S(DP)”) Index, and the S&P 500 Index. The S&P S(DP) Index includes a representative peer group of companies, and includes Paychex, Inc. Since September 1998, the Company has been a participant in the S&P 500 Index, a market group of companies with a larger than average market capitalization. All comparisons of stock price performance shown assume reinvestment of dividends.

14

Table of Contents

OTHER MATTERS AND INFORMATION

Proposals for Next Year’s Annual Meeting

      Stockholder proposals, which are intended to be presented at the 2005 Annual Meeting of Stockholders pursuant to SEC Rule 14a-8, must be received by the Company at its executive offices on or before May 3, 2005. Any such proposals must be submitted in accordance with applicable SEC rules and regulations.

      Stockholder proposals, which are intended to be presented at the 2005 Annual Meeting of Stockholders and which are submitted other than in accordance with the procedures specified in SEC Rule 14a-8, will be considered untimely if not received by the Company’s Secretary at least 45 days prior to the anniversary of the date on which the Company first mailed its proxy materials for its immediately preceding Annual Meeting of Stockholders.

Certain Relationships and Related Transactions

      Mr. Tucci is the President and Chief Executive Officer of EMC Corporation. During fiscal 2004, the Company purchased through negotiated transactions approximately $1.2 million of data processing equipment and software from EMC Corporation. Mr. Golisano is the owner of Rochester Aviation, Inc. from which the Company purchased approximately $120,000 of aviation services in fiscal 2004. Mr. Golisano also owns the Buffalo Sabres of the National Hockey League, for which the Company provided payroll and other human resource services. In fiscal 2004, the Buffalo Sabres paid the Company approximately $67,000 for these services.

Other Actions at the Annual Meeting

      As of the date of this Proxy Statement, management does not intend to present, and has not been informed that any other person intends to present, any matter for action at the Annual Meeting other than those described in this Proxy Statement. If any other matters properly come before the Annual Meeting, the persons named in the enclosed proxy will vote on such matters in accordance with their judgment.

	By order of the Board of Directors,
	John M. Morphy
	Secretary

Rochester, New York

15

Table of Contents

APPENDIX A

PAYCHEX, INC.

AUDIT COMMITTEE OF THE BOARD OF DIRECTORS

CHARTER

I.  PURPOSE

      The primary function of the Audit Committee is to assist the Board of Directors in fulfilling its oversight responsibilities to the shareholders, potential shareholders and the investment community by reviewing: financial reports and other financial information provided by the Company to governmental bodies or the public; the Company’s systems of internal controls and the Company’s auditing, accounting and financial reporting processes. Consistent with this function, the Audit Committee should encourage continuous improvement of, and should foster adherence to, the Company’s policies, procedures and practices at all levels. The Audit Committee’s primary duties and responsibilities are to:

	•	Serve as an independent and objective party to monitor the Company’s financial reporting process and internal control system.
	•	Review and appraise the audit efforts of the Company’s independent accountants and internal audit department.
	•	Provide an open avenue of communication among the independent accountants, financial and senior management, the internal auditing department, and the Board of Directors.

      The Audit Committee has the authority to conduct any investigation appropriate to fulfilling its responsibilities, and it has direct access to the independent auditors as well as anyone in the organization. The Audit Committee has the ability to retain, at the Company’s expense, special legal, accounting, or other consultants or experts it deems necessary in the performance of its duties.

II.  COMPOSITION

      The Audit Committee shall be comprised of at least three directors who meet the independence and experience requirements of Nasdaq. The members shall be appointed by the Board. The Board will designate a Chairman who will also be the primary contact to management, the independent accountants and the manager of Internal Audit during the time periods between the formal Audit Committee meetings and will meet the financial sophistication and background requirements of the SEC and Nasdaq rules.

      All members of the Committee shall have a working familiarity with basic finance and accounting practices, and at least one member of the Committee shall have accounting or related financial management expertise.

III.  MEETINGS

      The Committee shall meet at least six times annually and participation can be in person or telephonic. Four of the meetings will be held prior to the quarterly earnings releases and two general meetings will be held during the fiscal year. The Committee shall make regular reports to the Board. As part of its job to foster open communication, the Committee should ensure management, the manager of the internal audit department and the independent accountants are present at these meetings. The Committee will complete each meeting with the following exit protocol, the Committee will meet individually with the manager of the internal auditing department and then with the independent accountants to discuss any matters that the Committee or each of these groups believes should be discussed privately. The independent accountants will have access to the full Board of Directors if the independent accountants determine it is necessary.

A-1

Table of Contents

IV.  RESPONSIBILITIES AND DUTIES

      To fulfill its responsibilities and duties the Audit Committee shall:

	1. Review and update this Charter at least annually and recommend any proposed changes to the full Board of Directors for their approval.
	2. Review the Company’s annual audited financial statements prior to filing or distribution. Review should include discussion with management and independent auditors of significant issues regarding accounting principles, practices, financial reporting issues and judgments as well as the adequacy of internal controls that could significantly affect the Company’s financial statements.
	3. Review significant financial risk exposures and the steps management has taken to monitor, control and report such exposures. Review significant findings prepared by the independent auditors and the internal auditing department together with management’s responses.
	4. Review with financial management and the independent auditors the Company’s quarterly financial results prior to the release of earnings and/or the Company’s quarterly financial statements including a draft of Management’s Discussion and Analysis of Financial Condition and Results of Operations prior to filing or distribution. Discuss significant changes to the Company’s accounting principles and any items required to be communicated by the independent auditors in accordance with auditing standards.
	5. Recommend to the Board of Directors the selection of the independent accountants, which firm is ultimately accountable to the Audit Committee and the Board. Pre-approve the fees to be paid to the independent accountants. On an annual basis, the Committee should review and discuss with the accountants all significant relationships the accountants have with the Company to determine the accountants’ independence consistent with Independence Standards Board Standard Number 1.
	6. Review the performance of the independent accountants and approve any proposed discharge of the independent accountants when circumstances warrant.
	7. Periodically consult with the independent accountants out of the presence of management about internal controls and the fullness and accuracy of the organization’s financial statements.
	8. Consider the independent accountants’ judgments about the quality and appropriateness of the Company’s accounting principles as applied in its financial reporting.
	9. Receive periodic reports regarding any significant judgments made in management’s preparation of the financial statements and the appropriateness of such judgments.
	10. Following completion of the annual audit, review separately with each of management, the independent accountants and the internal audit manager any significant difficulties encountered during the course of the audit, including any restrictions on the scope of work or access to required information. The Committee will provide management with a manually signed document approving the year end financial statements.
	11. Review any significant disagreement among management and the independent accountants or the Internal Audit department in connection with the preparation of the financial statements.
	12. Review with the independent accountants, the internal audit manager and management the extent to which changes or improvements in financial or accounting practices, as approved by the Audit Committee, have been implemented.
	13. Establish, review and update periodically a code of ethics and ensure that management has established a system to enforce this code.
	14. Review activities, organizational structure, and qualifications of the internal audit department.
	15. Perform any other activities and prepare any other reports consistent with this Charter, the Company’s By-laws and applicable federal or state law, as the Committee or the Board deems necessary or appropriate.

A-2

Table of Contents

	16. Review, at least annually, report(s) from management concerning legal and regulatory matters that may have a material impact on the financial statements.
	17. The manager of internal audit is required to annually document in the form of a memorandum the actions of the Audit Committee, which indicate compliance with the Charter. This memo will be presented to the Audit Committee at the July Audit Committee Meeting.
	18. Establish procedures for the receipt, retention, and treatment of complaints received by the Company regarding accounting, internal accounting controls, or auditing matters, and for the confidential, anonymous submission by employees of concerns regarding questionable accounting or auditing matters.

      While the Audit Committee has the responsibilities and powers set forth in this Charter, it is not the duty of the Audit Committee to plan or conduct audits or to determine that the Company’s financial statements are complete and accurate and are in accordance with generally accepted accounting principles. This is the responsibility of management and the independent auditor. Nor is it the duty of the Audit Committee to conduct investigations, to resolve disagreements, if any, between management and the independent auditor or to assure compliance with laws and regulations and the Company’s code of ethics.

A-3

Table of Contents

APPENDIX B

PAYCHEX, INC.

COMPENSATION COMMITTEE OF THE BOARD OF DIRECTORS

CHARTER

I.  PURPOSE

      The primary purpose of the Compensation Committee is to assist the Board in discharging its responsibilities in respect of compensation of the Company’s Board of Directors, Chief Executive Officer, and senior executive officers.

II.  COMPOSITION

      The Compensation Committee shall be comprised of at least three external directors who meet the independence and experience requirements of the Nasdaq Stock Market, Inc. and have not been previously employed by the Company. The members shall be appointed and replaced by the Board. The Board will designate a Chairman who will also be the primary contact to management.

III.  MEETINGS

      The Committee shall meet at least three times a year. Additional meetings may occur as the Committee or its Chair deems advisable. Participation can be in person or telephonic.

IV.  RESPONSIBILITIES AND DUTIES

      To fulfill its responsibilities and duties the Compensation Committee shall:

	1. Review and recommend the Company’s goals and objectives relevant to CEO and senior executive officer compensation, evaluate the performance of the CEO and senior executive officers in light of those goals and objectives, and set the annual compensation level for the CEO and senior executive officers based on performance evaluations and compensation principles.
	2. Annually report on the CEO’s performance and compensation to the Board.
	3. Annually evaluate the appropriate level and form of compensation for Board and committee service by non-employee members of the Board and recommend changes to the Board when appropriate.
	4. Approve and make recommendations to the Board with respect to incentive compensation plans and equity-based compensation plans, including amendments, and approve and ratify awards made under such plans.
	5. Review executive compensation disclosures and report on executive compensation in the Company’s proxy statements.
	6. Review with management, plans for the orderly development and the succession of senior executive officers.
	7. Annually review and reassess the adequacy of this Charter and recommend any proposed changes to the Board for approval.
	8. Annually evaluate the Compensation Committee’s performance.
	9. Perform any other activities consistent with this Charter, the Company’s By-laws, Articles of Incorporation and governing law as the Board considers appropriate or delegates to the Compensation Committee, including duties assigned to it in the Company’s equity-based compensation plans, qualified retirement plans or other plans.

B-1

Table of Contents

V.  OUTSIDE ADVISORS

      The Compensation Committee has the authority, at the Company’s expense, (1) to retain, to determine the fees and other terms of engagement, and to terminate a compensation consultant to assist it regarding the CEO’s and senior executive officers’ compensation or (2) to engage the services of other advisors to assist it in the discharge of its duties. At least once every three years the Compensation Committee will retain a compensation consultant to give a report on whether the current compensation programs and agreements provide an appropriate level of compensation to senior executive officers and Board and whether they provide sufficient retention incentive.

B-2

Table of Contents

APPENDIX C

PAYCHEX, INC.

INVESTMENT COMMITTEE OF THE BOARD OF DIRECTORS

CHARTER

I.  PURPOSE

      The primary purpose of the Investment Committee is to assist the Board in reviewing investment policies, strategies and performance of the Company and its subsidiaries.

II.  COMPOSITION

      The Committee shall be composed of at least three Directors who meet the independence and experience requirements of the Nasdaq Stock Market, Inc. The members shall be appointed and replaced by the Board. The Board will designate a Chairman who will also be the primary contact to management.

III.  MEETINGS

      The Committee shall meet at least once a year. Additional meetings may occur as the Committee or its Chair deems advisable. Participation can be in person or telephonic.

IV.  RESPONSIBILITIES AND DUTIES

      To fulfill its responsibilities and duties the Investment Committee shall:

	1. Review the investment policies, strategies, and programs of the Company and its subsidiaries to ensure they are consistent with the goals and objectives of the Company;
	2. Determine that investment constraints are consistently followed and that procedures are in place to ensure that the investment portfolio is managed in compliance with the investment policy and applicable investment constraints;
	3. Delegate authority to management to execute individual investment transactions on behalf of the Company within policies and limits approved by the Committee;
	4. Approve all external investment manager changes;
	5. Review the performance of the investment portfolios of the Company and its subsidiaries;
	6. Make periodic reports to the Board;
	7. Annually review and reassess the adequacy of this Charter and recommend any proposed changes to the Board for approval;
	8. Have the authority to hire legal, accounting, financial or other advisors as they may deem necessary in their judgment with due regard to cost, without the need to obtain the prior approval of any officer of the Company.

C-1

Table of Contents

APPENDIX D

PAYCHEX, INC.

GOVERNANCE AND COMPENSATION COMMITTEE

CHARTER

I.  PURPOSES

      The primary purposes of the Governance and Compensation Committee (the “Committee”) are to assist the Board of Directors (the “Board”) in discharging its responsibilities with respect to the following:

	1. Evaluating and determining compensation of members of the Board, Chief Executive Officer, and senior executive officers;
	2. Providing general oversight with respect to the governance of the Board to ensure that the Board meets its fiduciary obligations to the Company and its stockholders; and
	3. Identifying, evaluating and recommending to the Board candidates for nomination for election to the Board.

II.  COMPOSITION

      The Committee shall be comprised of three or more external directors, each of whom satisfies applicable committee composition requirements, including the independence and experience requirements of the Nasdaq Stock Market, Inc. The Committee members shall be appointed and removed by the Board. The Board will designate a Committee Chair who will also be the primary contact to management.

III.  MEETINGS

      The Committee shall meet at least three times per year. Additional meetings may occur as the Committee or its Chair deems advisable. Attendance and participation may be in person or telephonic.

IV.  RESPONSIBILITIES AND DUTIES

      To fulfill its responsibilities and duties the Committee shall:

	1. Review and recommend the Company’s goals and objectives relevant to CEO and senior executive officer compensation, evaluate the performance of the CEO and senior executive officers in light of those goals and objectives, and set the annual compensation level for the CEO and senior executive officers based on performance evaluations and compensation principles.
	2. Annually report on the CEO’s performance and compensation to the Board.
	3. Annually evaluate the appropriate level and form of compensation for Board and committee service by non-employee members of the Board and recommend changes to the Board when appropriate.
	4. Approve and make recommendations to the Board with respect to incentive compensation plans and equity-based compensation plans, including amendments, and approve and ratify awards made under such plans.
	5. Review executive compensation disclosures and report on executive compensation in the Company’s proxy statements.
	6. Review with management plans for the orderly development and the succession of senior executive officers.
	7. Assist the Board in evaluating the current composition, organization and governance of the Board and its Committees and in determining future requirements.

D-1

Table of Contents

	8. Assist the Board in the evaluation and selection of members of Board committees and the selection of Board Committee chairs.
	9. Generally advise the Board on corporate governance matters.
	10. Assist the Board in identifying and evaluating nominees for election to the Board in accordance with the Board of Directors Nomination Policy attached hereto.
	11. Assist the Board in the evaluation and termination of membership of individual directors for cause or for other appropriate reasons.
	12. Assist the Board in conducting an annual review on succession planning, and work with the Board in evaluating potential successors to executive management positions.
	13. Annually review and make recommendations about changes to the charters of other Board Committees after consultation with the respective committee chairs.
	14. Make regular reports to the Board.
	15. Annually review and reassess the adequacy of this Charter and recommend any proposed changes to the Board for approval.
	16. Annually review and evaluate its own performance.

V.  OUTSIDE ADVISORS

      The Committee has the authority, at the Company’s expense, to retain, to determine the fees and other terms of engagement, and to terminate the engagement of consultants and advisors, which assist it in the discharge of its duties. At least once every three years the Governance and Compensation Committee will retain a compensation consultant to give a report on whether the current compensation programs and agreements provide an appropriate level of compensation to senior executive officers and Board and whether they provide sufficient retention incentive.

D-2

Table of Contents

PAYCHEX, INC.

BOARD OF DIRECTORS NOMINATION POLICY

      The Board of Directors of Paychex, Inc. (the “Company”) has determined that it is necessary for the continued success of the Company to ensure that the Board is composed of individuals having a variety of complementary experience, education, training and relationships relevant to the needs of the Board and the Company. Accordingly, the Board has adopted the following policies for the Governance and Compensation Committee (the “Committee”) in identifying and recommending to the Board candidates for nomination for election to the Board:

	1. The Committee shall consider candidates for nomination recommended by any reasonable source, including the Company’s officers and incumbent directors, as well as recommendations by stockholders submitted in accordance with the Company’s policies for stockholder communications with the Board.
	2. In identifying candidates for nomination to fill vacancies created by the expiration of the term of any incumbent director, the Committee shall determine whether such incumbent director is willing to stand for re-election to the Board and, if so, shall take into consideration the value to the Board and to the Company of continuity and familiarity with the Company’s business inherent in nominating the incumbent director.
	3. In evaluating any candidate for nomination to the Board, the Committee shall consider the contribution that such candidate would be expected to make to the Board and the Company based upon the current composition and needs of the Board and such candidate’s demonstrated business judgment, leadership abilities, integrity, prior experience, education, training, relationships and other factors that the Board determines relevant.

D-3

Table of Contents

Table of Contents

Table of Contents

Table of Contents