UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, DC 20549

FORM 11-K

(Mark One):

For the fiscal year ended December 31, 2011

OR

For the transition period from                     to                     

Commission file number 0-11330

Paychex, Inc. 401(k)

Incentive Retirement Plan

(Full title of the Plan)

Paychex, Inc.

911 Panorama Trail South

Rochester, NY 14625

(Name of issuer of the securities held pursuant to the Plan and the address of its principal executive office)

Index to Financial Statements, Schedule and Exhibits

SIGNATURES

The Plan. Pursuant to the requirements of the Securities Exchange Act of 1934, the Plan Committee has duly caused this annual report to be signed on its behalf by the undersigned hereunto duly authorized.

June 28, 2012:

2

Report of Independent Registered Public Accounting Firm

The Plan Committee

Paychex, Inc. 401(k)

Incentive Retirement Plan

Rochester, New York 14625

We have audited the accompanying statements of net assets available for benefits of the Paychex, Inc. 401(k) Incentive Retirement Plan as of December 31, 2011 and 2010, and the related statements of changes in net assets available for benefits for the years then ended. These financial statements are the responsibility of the Plan’s management. Our responsibility is to express an opinion on these financial statements based on our audits.

We conducted our audits in accordance with the standards of the Public Company Accounting Oversight Board (United States). Those standards require that we plan and perform the audit to obtain reasonable assurance about whether the financial statements are free of material misstatement. We were not engaged to perform an audit of the Plan’s internal control over financial reporting. Our audits included consideration of internal control over financial reporting as a basis for designing audit procedures that are appropriate in the circumstances, but not for the purpose of expressing an opinion on the effectiveness of the Plan’s internal control over financial reporting. Accordingly, we express no such opinion. An audit also includes examining, on a test basis, evidence supporting the amounts and disclosures in the financial statements, assessing the accounting principles used and significant estimates made by management, and evaluating the overall financial statement presentation. We believe that our audits provide a reasonable basis for our opinion.

In our opinion, the financial statements referred to above present fairly, in all material respects, the net assets available for benefits of the Plan at December 31, 2011 and 2010, and the changes in its net assets available for benefits for the years then ended, in conformity with U.S. generally accepted accounting principles.

Our audits were conducted for the purpose of forming an opinion on the financial statements taken as a whole. The accompanying supplemental schedule of assets (held at end of year) as of December 31, 2011, is presented for purposes of additional analysis and is not a required part of the financial statements but is supplementary information required by the Department of Labor’s Rules and Regulations for Reporting and Disclosure under the Employee Retirement Income Security Act of 1974. Such information is the responsibility of the Plan’s management. The information has been subjected to the auditing procedures applied in our audits of the financial statements and, in our opinion, is fairly stated in all material respects in relation to the financial statements taken as a whole.

/s/ Ernst & Young LLP

Hartford, Connecticut

June 28, 2012

3

PAYCHEX, INC. 401(k) INCENTIVE RETIREMENT PLAN

STATEMENT OF NET ASSETS AVAILABLE FOR BENEFITS

(In Thousands)

See accompanying notes to financial statements.

4

PAYCHEX, INC. 401(k) INCENTIVE RETIREMENT PLAN

STATEMENT OF CHANGES IN NET ASSETS AVAILABLE FOR BENEFITS

(In Thousands)

See accompanying notes to financial statements.

5

PAYCHEX, INC. 401(k) INCENTIVE RETIREMENT PLAN

NOTES TO FINANCIAL STATEMENTS

DECEMBER 31, 2011 and 2010

NOTE A. PLAN DESCRIPTION

The following brief description of the Paychex, Inc. (the “Company” or “Paychex”) 401(k) Incentive Retirement Plan (the “Plan”) is provided for general information purposes only. More complete information regarding the Plan’s provisions may be found in the Plan Document and Summary Plan Description.

General: The Plan is a defined contribution plan qualified under Sections 401(a) of the Internal Revenue Code (the “Code”), which includes provisions under Section 401(k) allowing an eligible participant to direct the employer to contribute a portion of the participant’s compensation to the Plan on a pre-tax and/or after-tax basis through payroll deductions. The Plan is subject to the provisions of the Employee Retirement Income Security Act of 1974, as amended (“ERISA”). The Plan was established on July 1, 1984 and restated in April 2002, January 2007, and October 2011 to include legislative and other applicable regulatory developments through October 1, 2011, as well as make other changes and enhancements to the Plan.

The Plan operates in part as an employee stock ownership plan (“ESOP”), which is designed to comply with Section 4975(e) and the regulations under the Code. It is not currently intended that the Plan be a leveraged ESOP, although the Plan permits the ESOP to borrow money to purchase ESOP stock if the employer should so elect at some future date. As of December 31, 2011 and 2010, all shares of ESOP stock are allocated to participant accounts. Under this ESOP feature, participants are able to receive dividends on their shares of Paychex common stock in the form of cash or have them reinvested into the Paychex ESOP Stock Fund (“ESOP Fund”).

Plan Mergers: On February 8, 2011, Paychex acquired SurePayroll, Inc. and on July 1, 2011, 127 participants of the

SurePayroll 401(k) (“SurePayroll Plan”) became participants in the Plan. Service time recognized under the SurePayroll Plan is also recognized for eligibility and vesting purposes under the Plan. Effective September 19, 2011, the SurePayroll Plan was merged with and into the Plan. The increase in net assets available for benefits resulting from this merger was approximately $2,296,000.

On May 3, 2011, Paychex acquired Fast401k, Inc (d/b/a ePlan Services, Inc.) and on October 1, 2011, 41 participants of the Fast401k, Inc. 401k Plan (“Fast401k Plan”) became participants in the Plan. Service time recognized under the Fast401k Plan is also recognized for eligibility and vesting purposes under the Plan. Effective December 30, 2011, the Fast 401k Plan was merged with and into the Plan. The increase in net assets available for benefits resulting from this merger was approximately $1,631,000.

Plan Amendments: During 2011 there were two amendments to the plan to authorize the plan mergers. There were no amendments to the plan in 2010. There was a resolution that was approved during 2010 to reinstate the employer matching contribution effective for pay dates after January 1, 2011.

6

NOTE A. PLAN DESCRIPTION (continued)

Plan Administration: The Plan is administered by the Paychex, Inc. 401(k) Incentive Retirement Plan Committee (the “Plan Committee”), which is appointed by the Board of Directors of the Company. The Plan’s trustee and record keeper is Fidelity Management Trust Company (“Fidelity”), who is also the trustee for the ESOP Fund. Fidelity was responsible for the custody and management of the Plan’s assets for the periods noted.

Eligible Employees: All new employees of the Company and its participating subsidiaries are eligible to participate in the salary deferral portion of the Plan immediately. Employees must be employed for one year in which a minimum of 1,000 hours have been worked to be eligible to receive a Company matching contribution, when such matching contribution is in effect.

Contributions: Employees may contribute, on a pre-tax basis and/or on an after-tax basis, from 1% up to 50% of their compensation through payroll deductions in increments of 1%, subject to the limitations established by the Code. For the Roth 401(k), employees may only contribute on an after-tax basis, subject to the same limitations as noted above. The maximum allowable annual employee contribution to the Plan was $16,500 in both 2011 and 2010. The Plan Committee may establish for any Plan year a contribution percentage limit for highly compensated employees that is less than 50%. Employees may also contribute amounts representing rollover distributions from other qualified defined benefit or defined contribution plans or individual retirement accounts.

The Company provided a matching contribution in the amount of 50% of up to 4% eligible pay that an employee contributed to the Plan, effective for pay dates on or after January 1, 2011. Prior to 2010, the Company suspended its safe harbor matching contribution and no matching contributions were made for pay dates in 2010. The Company increased the matching contribution in February 2012 to 50% of up to 6% of eligible pay that the employee contributes to the Plan. The Company may also elect to make an additional discretionary contribution to the Plan, but has not done so for the years ended December 31, 2011 and 2010.

Additionally, participants who are age 50 or older by the end of the calendar year are also allowed to make an additional “catch-up” contribution on a pre-tax basis and/or on an after-tax basis. For the Roth 401(k), participants “catch-up” contributions can only be made on an after-tax basis. This contribution was limited to $5,500 in both 2011 and 2010. The “catch-up” contributions are included in the match calculation, when such matching contribution is in effect, if the employee’s regular contribution is less than allowable percentage of eligible pay.

Vesting: Participants are fully vested as to their elective contributions and rollover contributions as well as any earnings or losses on them. Employees are fully vested immediately with respect to Company matching contributions made on or after September 1, 2007. For Company match contributions made prior to September 1, 2007, employees are fully vested upon completion of 1,000 hours of service per year for three calendar years. Employees are also fully vested upon disability, death, or the attainment of retirement age, which is age 65. Within the ESOP, dividends received are fully vested, regardless of years of service.

7

NOTE A. PLAN DESCRIPTION (continued)

Participant Accounts: The trustee maintains an account for each participant, including participant directed allocations to each investment fund. Each participant’s account is credited with the participant’s contribution and allocations of any employer contribution and Plan earnings, less loans and withdrawals. The investments under the Plan are 100% participant-directed. Plan participants can fully diversify their portfolios by choosing from any or all investment fund choices in the Plan. Transfers in and out of investment funds, including the ESOP Fund, are not restricted, with the exception of certain restricted trading periods for individuals designated as insiders as specified in the Paychex Insider Trading Policy. The Company matching contributions follow the same fund elections as the employee compensation deferrals.

Investment Options: As of December 31, 2011, participants may direct contributions in the following investment options:

Participants may choose to change their investment option choices and how their contributions are allocated to each fund chosen at any time. The Plan Committee regularly reviews performance, fees, and other key indicators of all investment options and may enter or exit funds at its discretion with the exception of the Paychex ESOP Stock Fund.

Forfeited Accounts: Forfeited non-vested assets are used to reduce future employer contributions. Total forfeitures used to reduce employer contributions were approximately $157,000 and $0 for 2011 and 2010, respectively. Forfeited balances not yet applied to reduce employer contributions as of December 31, 2011 and 2010, respectively, were not material to the financial statements.

8

NOTE A. PLAN DESCRIPTION (continued)

Participant Loans: The Plan allows participants to borrow from a minimum of $1,000 up to a maximum equal to the lesser of 50% of their vested account balance or $50,000, reduced by the highest outstanding loan balance in the previous twelve months. Only one loan may be outstanding at any time. The rate of interest is the United States (“U.S.”) prime lending rate plus 1% at the time the loan is disbursed. Payroll deductions are required to repay the principal and interest on the loan within four and one-half years, except for loans used for the purchase of a principal residence, which are required to be repaid within nine and one-half years. Participant loans are subject to a one-time, non-refundable loan origination fee of $75, which is deducted from the participant’s account.

Withdrawals: Withdrawals for financial hardship are permitted provided they are for a significant and immediate financial need, meet the applicable hardship criteria as outlined in the Code, and the distribution is necessary to satisfy that need. Participants are required to fully use the Plan loan program, described above, before requesting a hardship withdrawal and must exhaust all other eligible withdrawals available in the Plan. One hardship withdrawal may be taken each calendar year. For actively employed Plan participants, the Plan also allows for: partial withdrawals of vested balances at age 59  ¹/2; withdrawals of rollover contributions made prior to April 15, 2002; and withdrawals of dividends on the participant’s shares of Paychex common stock in the ESOP Fund in the form of cash, if desired.

Payment of Benefits: Upon separation from employment, at retirement, or reaching the age of 59  ¹/2, a participant may elect to receive either a lump-sum amount equal to the value of the participant’s vested interest in their account, or annual installments over a fixed period of time.

Participants in the ClearCourse Group Variable Annuity may elect to receive their vested interest as follows: full lifetime retirement income guarantee at the age of 65 or older; reduced lifetime retirement income guarantee between the ages of 55 and 64; and forfeiture of the lifetime retirement income guarantee prior to age 55.

Voting and Tender Offer Rights on ESOP Stock: Each participant in the ESOP Fund is entitled to exercise voting rights on shares held in their account and also direct the ESOP trustee to tender their shares of ESOP Stock if an offer is made to purchase such shares. If the participant does not vote or indicate their preference with respect to a tender offer, the trustee will vote the participant’s shares and unallocated shares in the same proportion as the shares for which the trustee has received instructions.

Plan Termination: Although it has not expressed any intent to do so, the Company has the right under the Plan to permanently discontinue contributions at any time and to terminate the Plan subject to the provisions of ERISA. In the event of Plan termination, participants will become fully vested in their account balances.

9

NOTE B. SUMMARY OF SIGNIFICANT ACCOUNTING POLICIES

Basis of Accounting: The financial statements of the Plan have been prepared on the accrual basis of accounting in accordance with U.S. generally accepted accounting principles (“GAAP”).

Use of Estimates: The preparation of financial statements in conformity with GAAP requires the Plan Committee to make estimates and assumptions that affect the amounts reported in the financial statements and accompanying notes. Actual results could differ from those estimates.

Investment Valuation and Income Recognition: Investments are reported at fair value. Fair value is the price that would be received to sell an asset or paid to transfer a liability in an orderly transaction between market participants at the measurement date. See Note D for discussion of fair value measurements.

Purchases and sales of securities are recorded on a trade date basis. Net realized gains or losses upon the sale of investments are based on their average cost. Dividends are recorded on the ex-dividend date. Interest income is recorded on the accrual basis.

Contributions: Contributions from the Company are accrued in accordance with the terms of the Plan. Participant contributions are recorded in the period the Company makes corresponding payroll deductions.

Notes Receivable from Participants: The principal amount of loans plus any unpaid accrued interest is reported as notes receivable from participants on the Statements of Net Assets Available for Benefits. Loans to participants have various maturity dates and interest rates range from 4.25% to 9.25%. Interest earned is recorded on an accrual basis as interest income on notes receivable from participants in the Statements of Changes in Net Assets Available for Benefits.

Payment of Benefits: Benefits are recorded when paid.

Recently Issued Accounting Pronouncements: In May 2011, the Financial Accounting Standards Board (“FASB”) issued guidance to amend certain measurement and disclosure requirements related to fair value measurements to improve consistency with international reporting standards. This guidance is effective prospectively for annual reporting periods beginning after December 15, 2011, and is applicable to the Plan’s year ended December 31, 2012. The Plan is currently evaluating this guidance, but does not expect its adoption will have a material effect on the financial statements.

Other recent accounting pronouncements issued by the FASB (including technical corrections to the FASB’s Accounting Standards Codification), and the American Institute of Certified Public Accountants did not, or are not, expected to have a material effect on the Plan’s net assets available for benefits or changes in net assets available for benefits.

Subsequent Events: The Plan has evaluated subsequent events for potential recognition and/or disclosure through the date of issuance of these financial statements.

10

NOTE C. INVESTMENTS

The following presents investments that represent 5% or more of the Plan’s net assets as of:

11

NOTE C. INVESTMENTS (continued)

The change in fair value of the Plan’s investments, including net realized and unrealized gains and losses, is as follows:

12

NOTE D. FAIR VALUE MEASUREMENTS

The carrying values of cash and contributions receivable approximate fair value due to the short maturities of these instruments. Notes receivable from participants are valued at the principal amount plus accrued interest, which approximates fair value. Mutual funds and Paychex common stock, which is the sole investment in the ESOP Fund, are stated at their approximate fair value based on quoted market prices. The Annuity Fund, ClearCourse Group Variable Annuity, is valued by Genworth Life and Annuity Insurance Company using the quoted market price of the underlying investments less applicable ClearCourse asset charges. Through June 2011, the underlying investments were GE Investment Funds, Inc.–Total Return Fund Class 2, then replaced by Janus Balanced T Share Class Fund. In determining the fair value of its assets and liabilities, the Plan uses various valuation approaches, predominantly the market and cost approaches.

The accounting standards related to fair value measurements include a hierarchy for information and valuations used in measuring fair value that is broken down into three levels based on reliability, as follows:

The preceding methods described may produce a fair value calculation that may not be indicative of net realizable value or reflective of future fair values. Furthermore, although the Plan believes its valuation methods are appropriate and consistent with other market participants, the use of different methodologies or assumptions to determine the fair value of certain financial instruments could result in a different fair value measurement at the reporting date.

The following table presents information on the Plan’s financial assets measured at fair value on a recurring basis as of:

13

NOTE D. FAIR VALUE MEASUREMENTS (continued)

The following table presents information on the Plan’s financial assets measured at fair value on a recurring basis as of:

NOTE E. RISKS AND UNCERTAINTIES

The Plan provides certain investments that are exposed to various risks, such as interest rate risk, credit risk, and market volatility risk. The Plan attempts to limit these risks by authorizing and offering participants a broad range of investment options that are invested in high quality securities or are offered and administered by reputable and known investment and insurance companies. Due to the level of risk associated with certain investment securities, it is reasonably possible that changes in values of investment securities will occur in the near term, and such changes could materially affect the amounts reported in the Statements of Net Assets Available for Benefits and of Changes in Net Assets Available for Benefits.

The Plan’s exposure to a concentration of risk is limited by the diversification of investments across 27 participant-directed fund elections. Additionally, the investments within each participant-directed fund election are further diversified into varied financial instruments, with the exception of the ESOP Fund, which invests in a single security and cash.

NOTE F. RELATED PARTY TRANSACTIONS

The Plan’s holdings of Paychex common stock qualify as a party-in-interest transaction. As of December 31, 2011, the Plan held 3,774,994 shares of Paychex common stock at a fair market value of $113,665,069. As of December 31, 2010, the Plan held 3,866,763 shares of Paychex common stock at a fair market value of $119,521,644.

Fidelity serves as trustee, recordkeeper, and custodian of the Plan and, therefore, is a party-in-interest. Administrative expenses of the Plan are paid by the Company. The Company paid approximately $253,000 and $184,000 in 2011 and 2010, respectively, in administrative expenses.

14

NOTE G. TAX STATUS

The Plan has received a determination letter from the Internal Revenue Service (“IRS”) dated May 21, 2008, stating that the Plan is qualified under Section 401(a) and Section 4975(e) of the Code and, therefore, the related trust is exempt from taxation. Subsequent to this determination by the IRS, the Plan was amended. Once qualified, the Plan is required to operate in conformity with the Code to maintain its qualification. The Plan Committee believes the Plan is being operated in compliance with the applicable requirements of the Code and, therefore, believes that the Plan, as amended, is qualified and the related trust is tax exempt.

The preparation of financial statements in conformity with GAAP requires the Plan Committee to evaluate tax positions taken by the Plan and recognize a tax liability (or asset) if the Plan has taken an uncertain position that more likely than not would not be sustained upon examination by the IRS. The Plan Committee has analyzed the tax positions taken by the Plan, and has concluded that as of December 31, 2011, there are no uncertain positions taken or expected to be taken that would require recognition of a liability (or asset) or disclosure in the financial statements, therefore the Plan has recognized no interest or penalties related to uncertain tax positions. The Plan is subject to routine audits by taxing jurisdictions; however, there are currently no audits for any tax periods in progress. The Plan Committee believes it is no longer subject to income tax examinations for the years prior to 2008.

NOTE H. RECONCILIATION OF FINANCIAL STATEMENTS TO IRS FORM 5500

As allowed by ERISA, the Plan has elected to prepare its IRS Form 5500 on the cash basis of accounting. The financial statements have been prepared on the accrual basis of accounting in accordance with GAAP. The following is a reconciliation between the net assets available for benefits as reported in the financial statements to the net assets available for benefits as reported in IRS Form 5500 as of:

15

SCHEDULE OF ASSETS (HELD AT END OF YEAR)

(SCHEDULE H, LINE 4i- FORM 5500)

PAYCHEX, INC. 401(k) INCENTIVE RETIREMENT PLAN

EIN-16-1124166

PLAN-0-40436

DECEMBER 31, 2011

(Dollars, Units, and Shares in Thousands)

16

SCHEDULE OF ASSETS (HELD AT END OF YEAR)

(SCHEDULE H, LINE 4i- FORM 5500) (continued)

PAYCHEX, INC. 401(k) INCENTIVE RETIREMENT PLAN

EIN-16-1124166

PLAN-0-40436

DECEMBER 31, 2011

(Dollars, Units, and Shares in Thousands)

17