Exhibit 5.1

Letterhead of Harter Secrest & Emery LLP

November 30, 2010

Paychex, Inc.
911 Panorama Trail South

Rochester, New York 14625

     Re:     Paychex, Inc. Registration Statement on Form S-8

Ladies and Gentlemen:

     We have acted as counsel to Paychex, Inc., a Delaware corporation (the “Company”), in connection with its filing of a Registration Statement on Form S-8 (the “Registration Statement”) with the Securities and Exchange Commission (the “SEC”) under the Securities Act of 1933, as amended (the “Securities Act”) with respect to the registration of an additional 10,000,000 shares of the Company’s common stock (the “Shares”), par value $0.01 per share, reserved for issuance pursuant to the terms of the Paychex, Inc. 2002 Stock Incentive Plan, as amended and restated effective October 13, 2010 (the “Plan”). This opinion is furnished to you at your request to enable you to fulfill the requirements of Item 601(b)(5) of Regulation S-K, 17 C.F.R. § 229.601(b)(5), in connection with the filing of the Registration Statement.

     For purposes of this opinion, we have with your permission made the following assumptions, in each case without independent verification: (i) the due authorization, execution and delivery of all documents by all the parties thereto; (ii) the genuineness of all signatures on all documents submitted to us; (iii) the authenticity and completeness of all documents, corporate records, certificates and other instruments (the “Records”) submitted to us; (iv) that photocopy, electronic, certified, conformed, facsimile and other copies submitted to us of the Records conform to the original Records; (v) the legal capacity of all individuals executing documents; (vi) that all documents are the valid and binding obligations of each of the parties thereto, enforceable against such parties in accordance with their respective terms and that no such documents have been amended or terminated orally or in writing; (vii) that the statements contained in the certificates and comparable documents of public officials, officers and representatives of the Company and other persons on which we have relied for the purposes of this opinion are true and correct; and (viii) that all of the Shares will be issued for the consideration permitted under the Plan as currently in effect, and none of such Shares will be issued for less than the par value per share. As to all questions of fact material to this opinion, we have relied (without independent investigation) upon certificates or comparable documents of officers and representatives of the Company.

     Based upon, subject to and limited by the foregoing, we are of the opinion that following (i) issuance of the Shares in accordance with the terms of the Plan and (ii) receipt by the Company of the consideration for the Shares as specified in the Plan, the Shares will be validly issued, fully paid, and nonassessable.

     We express no opinion with regard to the law of any jurisdiction other than the Delaware General Corporation Law, including the applicable provisions of the Delaware Constitution and the reported judicial decision interpreting such law, as in effect as of the date hereof.

     This opinion letter deals only with the specified legal issues expressly addressed herein, and you should not infer any opinion that is not explicitly addressed herein from any matter stated in this letter.

Page 2

     We consent to the use of this opinion as an exhibit to the Registration Statement. In giving such consent, we do not hereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act and the rules and regulations thereunder. This opinion is rendered to you as of the date hereof and we assume no obligation to advise you or any other person hereafter with regard to any change after the date hereof in the circumstances or the law that may bear on the matters set forth herein even though the changes may affect the legal analysis or legal conclusion or other matters in this letter.