<?xml version="1.0" encoding="us-ascii"?>
<!--XBRL document created with Bowne Tagger. XBRL Parser version 10.0.0.34-->
<!--Based on XBRL 2.1-->
<!--Created on: 5/12/2009 4:03:52 PM-->
<!--Modified on: 7/16/2010 3:25:14 PM-->
<schema xmlns="http://www.w3.org/2001/XMLSchema" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:xlink="http://www.w3.org/1999/xlink" targetNamespace="http://paychex.com/2010-05-31" xmlns:payx="http://paychex.com/2010-05-31" elementFormDefault="qualified" attributeFormDefault="unqualified" xmlns:us-types="http://xbrl.us/us-types/2009-01-31">
  <annotation>
    <appinfo>
      <link:roleType roleURI="http://paychex.com/role/ValuationAndQualifyingAccounts" id="ValuationAndQualifyingAccounts">
        <link:definition>0301 - Schedule - Valuation and Qualifying Accounts</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/RelatedParties" id="RelatedParties">
        <link:definition>0213 - Disclosure - Related Parties</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/OtherComprehensiveIncome" id="OtherComprehensiveIncome">
        <link:definition>0209 - Disclosure - Other Comprehensive Income</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/StockBasedCompensationPlans" id="StockBasedCompensationPlans">
        <link:definition>0202 - Disclosure - Stock-Based Compensation Plans</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/QuarterlyFinancialDataUnaudited" id="QuarterlyFinancialDataUnaudited">
        <link:definition>0214 - Disclosure - Quarterly Financial Data (Unaudited)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/EmployeeBenefitPlans" id="EmployeeBenefitPlans">
        <link:definition>0211 - Disclosure - Employee Benefit Plans</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/SupplementalCashFlowInformation" id="SupplementalCashFlowInformation">
        <link:definition>0210 - Disclosure - Supplemental Cash Flow Information</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/IncomeTaxes" id="IncomeTaxes">
        <link:definition>0208 - Disclosure - Income Taxes</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/StatementsOfStockholdersEquity" id="StatementsOfStockholdersEquity">
        <link:definition>0130 - Statement - Consolidated Statements of Stockholders' Equity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/FairValueMeasurements" id="FairValueMeasurements">
        <link:definition>0205 - Disclosure - Fair Value Measurements</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/CommitmentsAndContingencies" id="CommitmentsAndContingencies">
        <link:definition>0212 - Disclosure - Commitments and Contingencies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/GoodwillAndIntangibleAssetsNetOfAccumulatedAmortization" id="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortization">
        <link:definition>0207 - Disclosure - Goodwill and Intangible Assets, Net of Accumulated Amortization</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/PropertyAndEquipmentNetOfAccumulatedDepreciation" id="PropertyAndEquipmentNetOfAccumulatedDepreciation">
        <link:definition>0206 - Disclosure - Property and Equipment, Net of Accumulated Depreciation</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/FundsHeldForClientsAndCorporateInvestments" id="FundsHeldForClientsAndCorporateInvestments">
        <link:definition>0204 - Disclosure - Funds Held for Clients and Corporate Investments</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/BasicAndDilutedEarningsPerShare" id="BasicAndDilutedEarningsPerShare">
        <link:definition>0203 - Disclosure - Basic and Diluted Earnings Per Share</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/DescriptionOfBusinessAndSignificantAccountingPolicies" id="DescriptionOfBusinessAndSignificantAccountingPolicies">
        <link:definition>0201 - Disclosure - Description of Business and Significant Accounting Policies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/DocumentAndEntityInformation" id="DocumentAndEntityInformation">
        <link:definition>00 - Document - Document and Entity Information</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/StatementsOfCashFlows" id="StatementsOfCashFlows">
        <link:definition>0140 - Statement - Consolidated Statements of Cash Flows</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/StatementsOfIncome" id="StatementsOfIncome">
        <link:definition>0110 - Statement - Consolidated Statements of Income</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/BalanceSheetsParenthetical" id="BalanceSheetsParenthetical">
        <link:definition>0121 - Statement - Consolidated Balance Sheets (Parenthetical)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://paychex.com/role/BalanceSheets" id="BalanceSheets">
        <link:definition>0120 - Statement - Consolidated Balance Sheets</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:linkbaseRef xlink:type="simple" xlink:href="payx-20100531_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:title="Definition Links, all" />
      <link:linkbaseRef xlink:type="simple" xlink:href="payx-20100531_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:title="Presentation Links, all" />
      <link:linkbaseRef xlink:type="simple" xlink:href="payx-20100531_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:title="Calculation Links, all" />
      <link:linkbaseRef xlink:type="simple" xlink:href="payx-20100531_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:title="Label Links, all" />
    </appinfo>
  </annotation>
  <import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <import namespace="http://xbrl.us/dei/2009-01-31" schemaLocation="http://taxonomies.xbrl.us/us-gaap/2009/non-gaap/dei-2009-01-31.xsd" />
  <import namespace="http://xbrl.us/us-gaap/2009-01-31" schemaLocation="http://taxonomies.xbrl.us/us-gaap/2009/elts/us-gaap-2009-01-31.xsd" />
  <import namespace="http://xbrl.us/us-types/2009-01-31" schemaLocation="http://taxonomies.xbrl.us/us-gaap/2009/elts/us-types-2009-01-31.xsd" />
  <element id="payx_ClientFundObligations" name="ClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" />
  <element id="payx_CurrentLiabilitiesBeforeClientFundObligations" name="CurrentLiabilitiesBeforeClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" />
  <element id="payx_InterestOnFundsHeldForClients" name="InterestOnFundsHeldForClients" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" />
  <element id="payx_NetChangeInClientFundObligations" name="NetChangeInClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" />
  <element id="payx_NetChangeInFundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalents" name="NetChangeInFundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalents" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" />
  <element id="payx_DescriptionOfBusinessAndSignificantAccountingPoliciesAbstract" name="DescriptionOfBusinessAndSignificantAccountingPoliciesAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_FundsHeldForClientsAndCorporateInvestmentsAbstract" name="FundsHeldForClientsAndCorporateInvestmentsAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationAbstract" name="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_CommitmentsAndContingenciesAbstract" name="CommitmentsAndContingenciesAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_FundsHeldForClientsAndCorporateInvestmentsTextBlock" name="FundsHeldForClientsAndCorporateInvestmentsTextBlock" type="us-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_CurrentAssetsBeforeFundsHeldForClients" name="CurrentAssetsBeforeFundsHeldForClients" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" />
  <element id="payx_DescriptionOfBusinessAndSignificantAccountingPoliciesTextBlock" name="DescriptionOfBusinessAndSignificantAccountingPoliciesTextBlock" type="us-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_DocumentAndEntityInformationAbstract" name="DocumentAndEntityInformationAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_ProceedsFromAndExcessTaxBenefitRelatedToExerciseOfStockOptions" name="ProceedsFromAndExcessTaxBenefitRelatedToExerciseOfStockOptions" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" />
  <element id="payx_FairValueMeasurementsAbstract" name="FairValueMeasurementsAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <element id="payx_ProvisionForLitigationReserve" name="ProvisionForLitigationReserve" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" />
  <element id="payx_ValuationAndQualifyingAccountsAbstract" name="ValuationAndQualifyingAccountsAbstract" abstract="true" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
</schema>
