<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with Wdesk from Workiva-->
<!-- -->
<xsd:schema attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.paychex.com/20150531" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:nonnum="http://www.xbrl.org/dtr/type/non-numeric" xmlns:num="http://www.xbrl.org/dtr/type/numeric" xmlns:payx="http://www.paychex.com/20150531" xmlns:us-types="http://fasb.org/us-types/2014-01-31" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
  <xsd:import namespace="http://fasb.org/us-gaap/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-gaap-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-roles-2014-01-31.xsd" />
  <xsd:import namespace="http://fasb.org/us-types/2014-01-31" schemaLocation="http://xbrl.fasb.org/us-gaap/2014/elts/us-types-2014-01-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/arcrole/fact-explanatoryFact" schemaLocation="http://www.xbrl.org/lrr/arcrole/factExplanatory-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/non-numeric" schemaLocation="http://www.xbrl.org/dtr/type/nonNumeric-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/numeric" schemaLocation="http://www.xbrl.org/dtr/type/numeric-2009-12-16.xsd" />
  <xsd:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/country/2013-01-31" schemaLocation="http://xbrl.sec.gov/country/2013/country-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/currency/2014-01-31" schemaLocation="http://xbrl.sec.gov/currency/2014/currency-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2014-01-31" schemaLocation="http://xbrl.sec.gov/dei/2014/dei-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/exch/2014-01-31" schemaLocation="http://xbrl.sec.gov/exch/2014/exch-2014-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/invest/2013-01-31" schemaLocation="http://xbrl.sec.gov/invest/2013/invest-2013-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/naics/2011-01-31" schemaLocation="http://xbrl.sec.gov/naics/2011/naics-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/sic/2011-01-31" schemaLocation="http://xbrl.sec.gov/sic/2011/sic-2011-01-31.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/stpr/2011-01-31" schemaLocation="http://xbrl.sec.gov/stpr/2011/stpr-2011-01-31.xsd" />
  <xsd:annotation>
    <xsd:appinfo>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20150531_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20150531_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20150531_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple" />
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20150531_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple" />
      <link:roleType id="AccumulatedOtherComprehensiveIncome" roleURI="http://www.paychex.com/role/AccumulatedOtherComprehensiveIncome">
        <link:definition>2111100 - Disclosure - Accumulated 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 id="AccumulatedOtherComprehensiveIncomeDetails" roleURI="http://www.paychex.com/role/AccumulatedOtherComprehensiveIncomeDetails">
        <link:definition>2411402 - Disclosure - Accumulated Other Comprehensive Income (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="AccumulatedOtherComprehensiveIncomeTables" roleURI="http://www.paychex.com/role/AccumulatedOtherComprehensiveIncomeTables">
        <link:definition>2311301 - Disclosure - Accumulated Other Comprehensive Income (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BasicAndDilutedEarningsPerShare" roleURI="http://www.paychex.com/role/BasicAndDilutedEarningsPerShare">
        <link:definition>2102100 - 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 id="BasicAndDilutedEarningsPerShareBasicAndDilutedEarningsPerShareDetailsTextual" roleURI="http://www.paychex.com/role/BasicAndDilutedEarningsPerShareBasicAndDilutedEarningsPerShareDetailsTextual">
        <link:definition>2402403 - Disclosure - Basic and Diluted Earnings Per Share Basic and Diluted Earnings Per Share (Details Textual)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BasicAndDilutedEarningsPerShareDetails" roleURI="http://www.paychex.com/role/BasicAndDilutedEarningsPerShareDetails">
        <link:definition>2402402 - Disclosure - Basic and Diluted Earnings Per Share (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="BasicAndDilutedEarningsPerShareTables" roleURI="http://www.paychex.com/role/BasicAndDilutedEarningsPerShareTables">
        <link:definition>2302301 - Disclosure - Basic and Diluted Earnings Per Share (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingencies" roleURI="http://www.paychex.com/role/CommitmentsAndContingencies">
        <link:definition>2114100 - 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 id="CommitmentsAndContingenciesDetails" roleURI="http://www.paychex.com/role/CommitmentsAndContingenciesDetails">
        <link:definition>2414402 - Disclosure - Commitments and Contingencies (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesDetails1" roleURI="http://www.paychex.com/role/CommitmentsAndContingenciesDetails1">
        <link:definition>2414403 - Disclosure - Commitments and Contingencies (Details 1)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesDetails2" roleURI="http://www.paychex.com/role/CommitmentsAndContingenciesDetails2">
        <link:definition>2414404 - Disclosure - Commitments and Contingencies (Details 2)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesDetailsTextual" roleURI="http://www.paychex.com/role/CommitmentsAndContingenciesDetailsTextual">
        <link:definition>2414405 - Disclosure - Commitments and Contingencies (Details Textual)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CommitmentsAndContingenciesTables" roleURI="http://www.paychex.com/role/CommitmentsAndContingenciesTables">
        <link:definition>2314301 - Disclosure - Commitments and Contingencies (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ConsolidatedBalanceSheets" roleURI="http://www.paychex.com/role/ConsolidatedBalanceSheets">
        <link:definition>1002000 - 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:roleType id="ConsolidatedBalanceSheetsParenthetical" roleURI="http://www.paychex.com/role/ConsolidatedBalanceSheetsParenthetical">
        <link:definition>1002501 - 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 id="ConsolidatedStatementsOfCashFlows" roleURI="http://www.paychex.com/role/ConsolidatedStatementsOfCashFlows">
        <link:definition>1004000 - 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 id="ConsolidatedStatementsOfIncomeAndComprehensiveIncome" roleURI="http://www.paychex.com/role/ConsolidatedStatementsOfIncomeAndComprehensiveIncome">
        <link:definition>1001000 - Statement - Consolidated Statements of Income and 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 id="ConsolidatedStatementsOfStockholdersEquity" roleURI="http://www.paychex.com/role/ConsolidatedStatementsOfStockholdersEquity">
        <link:definition>1003000 - 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 id="DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPolicies" roleURI="http://www.paychex.com/role/DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPolicies">
        <link:definition>2101100 - Disclosure - Description of Business, Basis of Presentation, 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 id="DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesDetails" roleURI="http://www.paychex.com/role/DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesDetails">
        <link:definition>2401402 - Disclosure - Description of Business, Basis of Presentation, and Significant Accounting Policies (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesPolicies" roleURI="http://www.paychex.com/role/DescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesPolicies">
        <link:definition>2201201 - Disclosure - Description of Business, Basis of Presentation, and Significant Accounting Policies (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 id="DocumentAndEntityInformation" roleURI="http://www.paychex.com/role/DocumentAndEntityInformation">
        <link:definition>0001000 - 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 id="EmployeeBenefitPlans" roleURI="http://www.paychex.com/role/EmployeeBenefitPlans">
        <link:definition>2113100 - 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 id="EmployeeBenefitPlansDetails" roleURI="http://www.paychex.com/role/EmployeeBenefitPlansDetails">
        <link:definition>2413401 - Disclosure - Employee Benefit Plans  (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FairValueMeasurements" roleURI="http://www.paychex.com/role/FairValueMeasurements">
        <link:definition>2107100 - 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 id="FairValueMeasurementsDetails" roleURI="http://www.paychex.com/role/FairValueMeasurementsDetails">
        <link:definition>2407402 - Disclosure - Fair Value Measurements (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FairValueMeasurementsTables" roleURI="http://www.paychex.com/role/FairValueMeasurementsTables">
        <link:definition>2307301 - Disclosure - Fair Value Measurements (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FundsHeldForClientsAndCorporateInvestments" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestments">
        <link:definition>2106100 - 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 id="FundsHeldForClientsAndCorporateInvestmentsDetails" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestmentsDetails">
        <link:definition>2406402 - Disclosure - Funds Held for Clients and Corporate Investments (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FundsHeldForClientsAndCorporateInvestmentsDetails1" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestmentsDetails1">
        <link:definition>2406403 - Disclosure - Funds Held for Clients and Corporate Investments (Details 1)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FundsHeldForClientsAndCorporateInvestmentsDetails2" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestmentsDetails2">
        <link:definition>2406404 - Disclosure - Funds Held for Clients and Corporate Investments (Details 2)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FundsHeldForClientsAndCorporateInvestmentsDetailsCalc2" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestmentsDetailsCalc2">
        <link:definition>2406402 - Disclosure - Funds Held for Clients and Corporate Investments (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="FundsHeldForClientsAndCorporateInvestmentsTables" roleURI="http://www.paychex.com/role/FundsHeldForClientsAndCorporateInvestmentsTables">
        <link:definition>2306301 - Disclosure - Funds Held for Clients and Corporate Investments (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortization" roleURI="http://www.paychex.com/role/GoodwillAndIntangibleAssetsNetOfAccumulatedAmortization">
        <link:definition>2109100 - 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 id="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationDetails" roleURI="http://www.paychex.com/role/GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationDetails">
        <link:definition>2409402 - Disclosure - Goodwill and Intangible Assets, Net of Accumulated Amortization (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationDetailsTextual" roleURI="http://www.paychex.com/role/GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationDetailsTextual">
        <link:definition>2409403 - Disclosure - Goodwill and Intangible Assets, Net of Accumulated Amortization (Details Textual)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationTables" roleURI="http://www.paychex.com/role/GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationTables">
        <link:definition>2309301 - Disclosure - Goodwill and Intangible Assets, Net of Accumulated Amortization (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxes" roleURI="http://www.paychex.com/role/IncomeTaxes">
        <link:definition>2110100 - 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 id="IncomeTaxesDetails" roleURI="http://www.paychex.com/role/IncomeTaxesDetails">
        <link:definition>2410402 - Disclosure - Income Taxes (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesDetails1" roleURI="http://www.paychex.com/role/IncomeTaxesDetails1">
        <link:definition>2410403 - Disclosure - Income Taxes (Details 1)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesDetails2" roleURI="http://www.paychex.com/role/IncomeTaxesDetails2">
        <link:definition>2410404 - Disclosure - Income Taxes (Details 2)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesDetails3" roleURI="http://www.paychex.com/role/IncomeTaxesDetails3">
        <link:definition>2410405 - Disclosure - Income Taxes (Details 3)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesDetailsTextual" roleURI="http://www.paychex.com/role/IncomeTaxesDetailsTextual">
        <link:definition>2410406 - Disclosure - Income Taxes (Details Textual)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxesTables" roleURI="http://www.paychex.com/role/IncomeTaxesTables">
        <link:definition>2310301 - Disclosure - Income Taxes (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="InvestmentIncomeNetDetails" roleURI="http://www.paychex.com/role/InvestmentIncomeNetDetails">
        <link:definition>2404402 - Disclosure - Investment Income, Net (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="InvestmentIncomeNetNotes" roleURI="http://www.paychex.com/role/InvestmentIncomeNetNotes">
        <link:definition>2104100 - Disclosure - Investment Income, Net (Notes)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="InvestmentIncomeNetTables" roleURI="http://www.paychex.com/role/InvestmentIncomeNetTables">
        <link:definition>2304301 - Disclosure - Investment Income, Net (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipmentNetOfAccumulatedDepreciation" roleURI="http://www.paychex.com/role/PropertyAndEquipmentNetOfAccumulatedDepreciation">
        <link:definition>2108100 - 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 id="PropertyAndEquipmentNetOfAccumulatedDepreciationDetails" roleURI="http://www.paychex.com/role/PropertyAndEquipmentNetOfAccumulatedDepreciationDetails">
        <link:definition>2408402 - Disclosure - Property and Equipment, Net of Accumulated Depreciation (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="PropertyAndEquipmentNetOfAccumulatedDepreciationTables" roleURI="http://www.paychex.com/role/PropertyAndEquipmentNetOfAccumulatedDepreciationTables">
        <link:definition>2308301 - Disclosure - Property and Equipment, Net of Accumulated Depreciation (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnaudited" roleURI="http://www.paychex.com/role/QuarterlyFinancialDataUnaudited">
        <link:definition>2117100 - 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 id="QuarterlyFinancialDataUnauditedAdditionalDisclosuresDetails" roleURI="http://www.paychex.com/role/QuarterlyFinancialDataUnauditedAdditionalDisclosuresDetails">
        <link:definition>2417403 - Disclosure - Quarterly Financial Data (Unaudited) - Additional Disclosures (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnauditedDetails" roleURI="http://www.paychex.com/role/QuarterlyFinancialDataUnauditedDetails">
        <link:definition>2417402 - Disclosure - Quarterly Financial Data (Unaudited) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="QuarterlyFinancialDataUnauditedTables" roleURI="http://www.paychex.com/role/QuarterlyFinancialDataUnauditedTables">
        <link:definition>2317301 - Disclosure - Quarterly Financial Data (Unaudited) (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RelatedParties" roleURI="http://www.paychex.com/role/RelatedParties">
        <link:definition>2116100 - 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 id="RelatedPartiesDetails" roleURI="http://www.paychex.com/role/RelatedPartiesDetails">
        <link:definition>2416401 - Disclosure - Related Parties (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlans" roleURI="http://www.paychex.com/role/StockBasedCompensationPlans">
        <link:definition>2105100 - 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 id="StockBasedCompensationPlansDetails" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails">
        <link:definition>2405402 - Disclosure - Stock-Based Compensation Plans (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails1" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails1">
        <link:definition>2405403 - Disclosure - Stock-Based Compensation Plans (Details 1)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails2" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails2">
        <link:definition>2405404 - Disclosure - Stock-Based Compensation Plans (Details 2)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails3" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails3">
        <link:definition>2405405 - Disclosure - Stock-Based Compensation Plans (Details 3)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails4" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails4">
        <link:definition>2405406 - Disclosure - Stock-Based Compensation Plans (Details 4)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails5" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails5">
        <link:definition>2405407 - Disclosure - Stock-Based Compensation Plans (Details 5)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails6" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails6">
        <link:definition>2405408 - Disclosure - Stock-Based Compensation Plans (Details 6)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails7" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails7">
        <link:definition>2405409 - Disclosure - Stock-Based Compensation Plans (Details 7)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetails8" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetails8">
        <link:definition>2405410 - Disclosure - Stock-Based Compensation Plans (Details 8)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansDetailsTextuals" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansDetailsTextuals">
        <link:definition>2405411 - Disclosure - Stock-Based Compensation Plans (Details Textuals)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="StockBasedCompensationPlansTables" roleURI="http://www.paychex.com/role/StockBasedCompensationPlansTables">
        <link:definition>2305301 - Disclosure - Stock-Based Compensation Plans (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SupplementalCashFlowInformation" roleURI="http://www.paychex.com/role/SupplementalCashFlowInformation">
        <link:definition>2112100 - 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 id="SupplementalCashFlowInformationDetails" roleURI="http://www.paychex.com/role/SupplementalCashFlowInformationDetails">
        <link:definition>2412401 - Disclosure - Supplemental Cash Flow Information (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ValuationAndQualifyingAccounts" roleURI="http://www.paychex.com/role/ValuationAndQualifyingAccounts">
        <link:definition>2118100 - Disclosure - 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 id="ValuationAndQualifyingAccountsDetails" roleURI="http://www.paychex.com/role/ValuationAndQualifyingAccountsDetails">
        <link:definition>2418402 - Disclosure - Valuation and Qualifying Accounts (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="ValuationAndQualifyingAccountsTables" roleURI="http://www.paychex.com/role/ValuationAndQualifyingAccountsTables">
        <link:definition>2318301 - Disclosure - Valuation and Qualifying Accounts (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xsd:appinfo>
  </xsd:annotation>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingAfterFiveYearsAmortizedCost" name="AvailableForSaleSecuritiesDebtMaturitiesRollingAfterFiveYearsAmortizedCost" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingAfterYearFiveFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesRollingAfterYearFiveFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingYearFourandFiveAmortizedCostBasis" name="AvailableForSaleSecuritiesDebtMaturitiesRollingYearFourandFiveAmortizedCostBasis" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingYearFourandFiveFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesRollingYearFourandFiveFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingYearOneThroughThreeAmortizedCostBasis" name="AvailableForSaleSecuritiesDebtMaturitiesRollingYearOneThroughThreeAmortizedCostBasis" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesRollingYearOneThroughThreeFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesRollingYearOneThroughThreeFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesGrossUnrealizedGains1" name="AvailableForSaleSecuritiesGrossUnrealizedGains1" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableForSaleSecuritiesGrossUnrealizedLosses" name="AvailableForSaleSecuritiesGrossUnrealizedLosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableforsaleSecuritiesContinuousUnrealizedLossPositionTwelvemonthsorlongerAggregatelosses" name="AvailableforsaleSecuritiesContinuousUnrealizedLossPositionTwelvemonthsorlongerAggregatelosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableforsaleSecuritiesContinuousunrealizedlosspositionLessthantwelvemonthsAggregateLosses" name="AvailableforsaleSecuritiesContinuousunrealizedlosspositionLessthantwelvemonthsAggregateLosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_AvailableforsaleSecuritiesContinuousunrealizedlosspostitionAggregatelosses" name="AvailableforsaleSecuritiesContinuousunrealizedlosspostitionAggregatelosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="payx_ClassificationOfInvestmentsOnConsolidatedBalanceSheetsAbstract" name="ClassificationOfInvestmentsOnConsolidatedBalanceSheetsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ClassificationOfInvestmentsOnConsolidatedBalanceSheetsTableTextBlock" name="ClassificationOfInvestmentsOnConsolidatedBalanceSheetsTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ClientFundObligations" name="ClientFundObligations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="payx_CommitmentsAndContingenciesTextualAbstract" name="CommitmentsAndContingenciesTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_ComponentsOfFundsHeldForClientsAndCorporateInvestmentsAbstract" name="ComponentsOfFundsHeldForClientsAndCorporateInvestmentsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ComponentsOfFundsHeldForClientsAndCorporateInvestmentsTableTextBlock" name="ComponentsOfFundsHeldForClientsAndCorporateInvestmentsTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ConcentrationsPolicyTextBlock" name="ConcentrationsPolicyTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ConstructioninProgress" name="ConstructioninProgress" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_ContractualLifeOfStockOptionGrants" name="ContractualLifeOfStockOptionGrants" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_CurrentAssetsBeforeFundsHeldForClients" name="CurrentAssetsBeforeFundsHeldForClients" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_CurrentLiabilitiesBeforeClientFundObligations" name="CurrentLiabilitiesBeforeClientFundObligations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_DataProcessingEquipmentGross" name="DataProcessingEquipmentGross" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_DataProcessingEquipmentMember" name="DataProcessingEquipmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_DefinedContributionPlanPercentageOfEligibleEmployeePayMatchedByEmployer" name="DefinedContributionPlanPercentageOfEligibleEmployeePayMatchedByEmployer" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_DocumentAndEntityInformationAbstract" name="DocumentAndEntityInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_EmcCorporationMember" name="EmcCorporationMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_EmployeeBenefitPlansAbstract" name="EmployeeBenefitPlansAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_EmployeesDeferredCompensationPlansDeferredPercentageMaximum" name="EmployeesDeferredCompensationPlansDeferredPercentageMaximum" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_EquityActivityRelatedToStockBasedAwards" name="EquityActivityRelatedToStockBasedAwards" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="payx_ExpiryDateRangeOfLettersOfCredit" name="ExpiryDateRangeOfLettersOfCredit" nillable="true" substitutionGroup="xbrli:item" type="us-types:dateStringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_FinancialInstitutionFourMember" name="FinancialInstitutionFourMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_FinancialInstitutionOneMember" name="FinancialInstitutionOneMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_FinancialInstitutionThreeMember" name="FinancialInstitutionThreeMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_FinancialInstitutionTwoMember" name="FinancialInstitutionTwoMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_FundsHeldForClientsAndCorporateInvestmentsAbstract" name="FundsHeldForClientsAndCorporateInvestmentsAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsAmortizedCost" name="FundsHeldForClientsAndCorporateInvestmentsAmortizedCost" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsDisclosureTextBlock" name="FundsHeldForClientsAndCorporateInvestmentsDisclosureTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsFairValue" name="FundsHeldForClientsAndCorporateInvestmentsFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedGains" name="FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedGains" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedLosses" name="FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedLosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element abstract="true" id="payx_FundsHeldForClientsAndCorporateInvestmentsTextualAbstract" name="FundsHeldForClientsAndCorporateInvestmentsTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsAmortizedCost" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsAmortizedCost" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsFairValue" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsGrossUnrealizedGains" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsGrossUnrealizedGains" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsGrossUnrealizedLosses" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsGrossUnrealizedLosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_FurnitureFixturesAndEquipmentGross" name="FurnitureFixturesAndEquipmentGross" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_FurnitureFixturesAndEquipmentMember" name="FurnitureFixturesAndEquipmentMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_GeneralObligationMunicipalBondsMember" name="GeneralObligationMunicipalBondsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationTextualAbstract" name="GoodwillAndIntangibleAssetsNetOfAccumulatedAmortizationTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_IncomeTaxesDetailsTextualAbstract" name="IncomeTaxesDetailsTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_IncreaseDecreaseResultingFromAbstract" name="IncreaseDecreaseResultingFromAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_IrrevocableStandbyLettersOfCreditAmountAvailable" name="IrrevocableStandbyLettersOfCreditAmountAvailable" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_LeaseIncentivesReceived" name="LeaseIncentivesReceived" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="payx_LiabilityForUncertainTaxPositionsCurrentAndNoncurrent" name="LiabilityForUncertainTaxPositionsCurrentAndNoncurrent" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_MaximumDaysinWhichPayrollTaxesWillBeRemittedAfterReceiptOfCollectionsFromClient" name="MaximumDaysinWhichPayrollTaxesWillBeRemittedAfterReceiptOfCollectionsFromClient" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_MaximumIndividualClaimsLiabilityHealthInsurance" name="MaximumIndividualClaimsLiabilityHealthInsurance" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="payx_MaximumIndividualClaimsLiabilityWorkersCompensationInsurance" name="MaximumIndividualClaimsLiabilityWorkersCompensationInsurance" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element id="payx_MaximumPeriodPayrollTaxesRemittedAfterReceiptOfCollectionsFromClient" name="MaximumPeriodPayrollTaxesRemittedAfterReceiptOfCollectionsFromClient" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_MaximummaturityperiodforVRDNsprimarilycategorizedasdueafterfiveyears" name="MaximummaturityperiodforVRDNsprimarilycategorizedasdueafterfiveyears" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_MinimummaturityperiodforVRDNsprimarilycategorizedasdueafter5years" name="MinimummaturityperiodforVRDNsprimarilycategorizedasdueafter5years" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_NatureOfOperationsPolicyTextBlock" name="NatureOfOperationsPolicyTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_NetChangeInClientFundObligations" name="NetChangeInClientFundObligations" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="payx_NetChangeInFundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalents" name="NetChangeInFundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalents" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element id="payx_Netunrealizedgainlossonavailableforsalesecurities" name="Netunrealizedgainlossonavailableforsalesecurities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_OtherSecuritiesAmortizedCost" name="OtherSecuritiesAmortizedCost" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_OtherSecuritiesFairValue" name="OtherSecuritiesFairValue" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_OtherSecuritiesGrossUnrealizedGains" name="OtherSecuritiesGrossUnrealizedGains" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_OtherSecuritiesGrossUnrealizedLosses" name="OtherSecuritiesGrossUnrealizedLosses" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_OutsideDirectorsDeferredCompensationPlansDeferredPercentageMaximum" name="OutsideDirectorsDeferredCompensationPlansDeferredPercentageMaximum" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_PEOhealthinsurancecostsincurrentliabilities" name="PEOhealthinsurancecostsincurrentliabilities" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_PerformancePeriodForUnearnedPerformanceShares" name="PerformancePeriodForUnearnedPerformanceShares" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_PerformanceStockOptionsMember" name="PerformanceStockOptionsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_PeriodInWhichPayrollTaxesTypicallyRemittedAfterReceiptOfCollectionsFromClient" name="PeriodInWhichPayrollTaxesTypicallyRemittedAfterReceiptOfCollectionsFromClient" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_PreRefundedMunicipalBondsMember" name="PreRefundedMunicipalBondsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_PropertyAndEquipmentNetOfAccumulatedDepreciationTextualAbstract" name="PropertyAndEquipmentNetOfAccumulatedDepreciationTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_QuarterlyFinancialDataUnauditedAbstract" name="QuarterlyFinancialDataUnauditedAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ReserveForClientFundLossesMember" name="ReserveForClientFundLossesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ReserveForUncertainTaxPositions" name="ReserveForUncertainTaxPositions" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element id="payx_RestrictedStockUnitMember" name="RestrictedStockUnitMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_RevenueMunicipalBondsMember" name="RevenueMunicipalBondsMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ScheduleOfShareBasedCompensationOtherInformationPertainingToRestrictedStockAwardsActivityTableTextBlockTableTextBlock" name="ScheduleOfShareBasedCompensationOtherInformationPertainingToRestrictedStockAwardsActivityTableTextBlockTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ScheduleOfShareBasedCompensationOtherInformationPertainingToRestrictedStockUnitsActivityTableTextBlock" name="ScheduleOfShareBasedCompensationOtherInformationPertainingToRestrictedStockUnitsActivityTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ScheduleOfShareBasedCompensationPerformanceStockOptionsActivityTableTextBlock" name="ScheduleOfShareBasedCompensationPerformanceStockOptionsActivityTableTextBlock" nillable="true" substitutionGroup="xbrli:item" type="nonnum:textBlockItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_ScheduleOfShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsOtherInformationAbstract" name="ScheduleOfShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsOtherInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_ScheduleOfShareBasedPaymentAwardStockOptionsOtherInformationAbstract" name="ScheduleOfShareBasedPaymentAwardStockOptionsOtherInformationAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsNonvestedIntrinsicValues" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsNonvestedIntrinsicValues" nillable="true" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element id="payx_ShareBasedCompensationArrangementByShareBasedPaymentAwardRestrictedStockUnitsWeightedAverageRemainingVestingPeriod" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardRestrictedStockUnitsWeightedAverageRemainingVestingPeriod" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_ShareRepurchaseProgram1Member" name="ShareRepurchaseProgram1Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_ShareRepurchaseProgram2Member" name="ShareRepurchaseProgram2Member" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_SharebasedCompensationArrangementbySharebasedPaymentAwardAwardVestingRightsActualPercentage" name="SharebasedCompensationArrangementbySharebasedPaymentAwardAwardVestingRightsActualPercentage" nillable="true" substitutionGroup="xbrli:item" type="num:percentItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_StaplesIncMember" name="StaplesIncMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_StockBasedCompensationPlansAbstract" name="StockBasedCompensationPlansAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_StockBasedCompensationPlansTextualAbstract" name="StockBasedCompensationPlansTextualAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element abstract="true" id="payx_TypeOfIssueAbstract" name="TypeOfIssueAbstract" nillable="true" substitutionGroup="xbrli:item" type="xbrli:stringItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_UnearnedPerformanceSharesMember" name="UnearnedPerformanceSharesMember" nillable="true" substitutionGroup="xbrli:item" type="nonnum:domainItemType" xbrli:periodType="duration" />
  <xsd:element id="payx_YearsofservicetobeeligibleforCompanymatchcontribution" name="YearsofservicetobeeligibleforCompanymatchcontribution" nillable="true" substitutionGroup="xbrli:item" type="xbrli:durationItemType" xbrli:periodType="duration" />
</xsd:schema>
