<?xml version="1.0" encoding="US-ASCII"?>
<!-- DFIN New ActiveDisclosure (SM) XBRL Schema Document - http://www.dfinsolutions.com/ -->
<!-- Creation Date :2022-12-22T14:53:34.8183+00:00 -->
<!-- Copyright (c) 2022 Donnelly Financial Solutions, Inc. All Rights Reserved. -->
<xsd:schema targetNamespace="http://www.paychex.com/20221130" attributeFormDefault="unqualified" elementFormDefault="qualified" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2020-01-21" xmlns:enum2="http://xbrl.org/2020/extensible-enumerations-2.0" xmlns:srt="http://fasb.org/srt/2022" xmlns:payx="http://www.paychex.com/20221130" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:us-gaap="http://fasb.org/us-gaap/2022" xmlns:dei="http://xbrl.sec.gov/dei/2022" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xlink="http://www.w3.org/1999/xlink">
  <xsd:import schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" namespace="http://www.xbrl.org/2003/instance"/>
  <xsd:import schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" namespace="http://www.xbrl.org/2003/linkbase"/>
  <xsd:import schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" namespace="http://xbrl.org/2005/xbrldt"/>
  <xsd:import schemaLocation="https://xbrl.sec.gov/dei/2022/dei-2022.xsd" namespace="http://xbrl.sec.gov/dei/2022"/>
  <xsd:import schemaLocation="https://xbrl.fasb.org/us-gaap/2022/elts/us-gaap-2022.xsd" namespace="http://fasb.org/us-gaap/2022"/>
  <xsd:import schemaLocation="https://www.xbrl.org/dtr/type/2020-01-21/types.xsd" namespace="http://www.xbrl.org/dtr/type/2020-01-21"/>
  <xsd:import schemaLocation="https://xbrl.fasb.org/srt/2022/elts/srt-2022.xsd" namespace="http://fasb.org/srt/2022"/>
  <xsd:annotation>
    <xsd:appinfo>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20221130_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:title="Labels link" xlink:type="simple"/>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20221130_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:title="Presentation link" xlink:type="simple"/>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20221130_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:title="Definition link" xlink:type="simple"/>
      <link:linkbaseRef xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="payx-20221130_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:title="Calculation link" xlink:type="simple"/>
      <link:roleType roleURI="http://www.paychex.com/20221130/taxonomy/role/DocumentDocumentAndEntityInformation" id="DocumentDocumentAndEntityInformation">
        <link:definition>100000 - 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://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedStatementsOfIncomeAndComprehensiveIncome" id="StatementConsolidatedStatementsOfIncomeAndComprehensiveIncome">
        <link:definition>100010 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedBalanceSheets" id="StatementConsolidatedBalanceSheets">
        <link:definition>100020 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedBalanceSheetsParenthetical" id="StatementConsolidatedBalanceSheetsParenthetical">
        <link:definition>100030 - 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://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedStatementsOfStockholdersEquity" id="StatementConsolidatedStatementsOfStockholdersEquity">
        <link:definition>100040 - 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://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedStatementsOfStockholdersEquityParenthetical" id="StatementConsolidatedStatementsOfStockholdersEquityParenthetical">
        <link:definition>100050 - Statement - Consolidated Statements of Stockholders' Equity (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://www.paychex.com/20221130/taxonomy/role/StatementConsolidatedStatementsOfCashFlows" id="StatementConsolidatedStatementsOfCashFlows">
        <link:definition>100060 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPolicies" id="DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPolicies">
        <link:definition>100070 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenue" id="DisclosureServiceRevenue">
        <link:definition>100080 - Disclosure - Service Revenue</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://www.paychex.com/20221130/taxonomy/role/DisclosureBasicAndDilutedEarningsPerShare" id="DisclosureBasicAndDilutedEarningsPerShare">
        <link:definition>100090 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureOtherIncomeexpenseNet" id="DisclosureOtherIncomeexpenseNet">
        <link:definition>100100 - Disclosure - Other Income/(Expense), Net</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://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestments" id="DisclosureFundsHeldForClientsAndCorporateInvestments">
        <link:definition>100110 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureFairValueMeasurements" id="DisclosureFairValueMeasurements">
        <link:definition>100120 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureSupplementalInformation" id="DisclosureSupplementalInformation">
        <link:definition>100130 - Disclosure - Supplemental 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://www.paychex.com/20221130/taxonomy/role/DisclosureCommitmentsAndContingencies" id="DisclosureCommitmentsAndContingencies">
        <link:definition>100140 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureIncomeTaxes" id="DisclosureIncomeTaxes">
        <link:definition>100150 - 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://www.paychex.com/20221130/taxonomy/role/DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesPolicy" id="DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesPolicy">
        <link:definition>100160 - Disclosure - Description of Business, Basis of Presentation, and Significant Accounting Policies (Policy)</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://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueTables" id="DisclosureServiceRevenueTables">
        <link:definition>100170 - Disclosure - Service Revenue (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureBasicAndDilutedEarningsPerShareTables" id="DisclosureBasicAndDilutedEarningsPerShareTables">
        <link:definition>100180 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureOtherIncomeexpenseNetTables" id="DisclosureOtherIncomeexpenseNetTables">
        <link:definition>100190 - Disclosure - Other Income/(Expense), 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsTables" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsTables">
        <link:definition>100200 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFairValueMeasurementsTables" id="DisclosureFairValueMeasurementsTables">
        <link:definition>100210 - 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesNarrativeDetails" id="DisclosureDescriptionOfBusinessBasisOfPresentationAndSignificantAccountingPoliciesNarrativeDetails">
        <link:definition>100220 - Disclosure - Description of Business, Basis of Presentation, and Significant Accounting Policies (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueNarrativeDetails" id="DisclosureServiceRevenueNarrativeDetails">
        <link:definition>100230 - Disclosure - Service Revenue (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueSummaryOfPeoPassThroughCostsNettedInRevenueDetails" id="DisclosureServiceRevenueSummaryOfPeoPassThroughCostsNettedInRevenueDetails">
        <link:definition>100240 - Disclosure - Service Revenue (Summary of PEO Pass-Through Costs Netted in Revenue) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueSummaryOfChangesInDeferredRevenueRelatedToMaterialRightsPerformanceObligationsDetails" id="DisclosureServiceRevenueSummaryOfChangesInDeferredRevenueRelatedToMaterialRightsPerformanceObligationsDetails">
        <link:definition>100250 - Disclosure - Service Revenue (Summary of Changes in Deferred Revenue Related to Material Rights Performance Obligations) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueSummaryOfDeferredRevenueRemainingPerformanceObligationExpectedTimingOfSatisfactionDetails" id="DisclosureServiceRevenueSummaryOfDeferredRevenueRemainingPerformanceObligationExpectedTimingOfSatisfactionDetails">
        <link:definition>100260 - Disclosure - Service Revenue (Summary of Deferred Revenue, Remaining Performance Obligation, Expected Timing of Satisfaction) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureServiceRevenueSummaryOfChangesInDeferredCostsToObtainAndFulfillContractsDetails" id="DisclosureServiceRevenueSummaryOfChangesInDeferredCostsToObtainAndFulfillContractsDetails">
        <link:definition>100270 - Disclosure - Service Revenue (Summary of Changes in Deferred Costs to Obtain and Fulfill Contracts) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureBasicAndDilutedEarningsPerShareBasicAndDilutedEarningsPerShareDetails" id="DisclosureBasicAndDilutedEarningsPerShareBasicAndDilutedEarningsPerShareDetails">
        <link:definition>100280 - Disclosure - Basic and Diluted Earnings Per Share (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureOtherIncomeexpenseNetScheduleOfOtherIncomeexpenseNetDetails" id="DisclosureOtherIncomeexpenseNetScheduleOfOtherIncomeexpenseNetDetails">
        <link:definition>100290 - Disclosure - Other Income/(Expense), Net (Schedule of Other Income/(Expense), 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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsFundsHeldForClientsAndCorporateInvestmentsDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsFundsHeldForClientsAndCorporateInvestmentsDetails">
        <link:definition>100300 - Disclosure - Funds Held for Clients and Corporate Investments (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsNarrativeDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsNarrativeDetails">
        <link:definition>100310 - Disclosure - Funds Held for Clients and Corporate Investments (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsClassificationOfInvestmentsOnConsolidatedBalanceSheetsDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsClassificationOfInvestmentsOnConsolidatedBalanceSheetsDetails">
        <link:definition>100320 - Disclosure - Funds Held for Clients and Corporate Investments (Classification of Investments on Consolidated Balance Sheets) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsSecuritiesInUnrealizedLossPositionDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsSecuritiesInUnrealizedLossPositionDetails">
        <link:definition>100330 - Disclosure - Funds Held for Clients and Corporate Investments (Securities in Unrealized Loss Position) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsRealizedGainsAndLossesFromSaleOfAvailableForSaleSecuritiesDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsRealizedGainsAndLossesFromSaleOfAvailableForSaleSecuritiesDetails">
        <link:definition>100340 - Disclosure - Funds Held for Clients and Corporate Investments (Realized Gains and Losses from Sale of Available-for-sale Securities) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFundsHeldForClientsAndCorporateInvestmentsAmortizedCostAndFairValueOfAvailableForSaleSecuritiesByContractualMaturityDetails" id="DisclosureFundsHeldForClientsAndCorporateInvestmentsAmortizedCostAndFairValueOfAvailableForSaleSecuritiesByContractualMaturityDetails">
        <link:definition>100350 - Disclosure - Funds Held for Clients and Corporate Investments (Amortized Cost and Fair Value of Available-for-Sale Securities by Contractual Maturity) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFairValueMeasurementsFinancialAssetsAndLiabilitiesMeasuredAtFairValueOnRecurringBasisDetails" id="DisclosureFairValueMeasurementsFinancialAssetsAndLiabilitiesMeasuredAtFairValueOnRecurringBasisDetails">
        <link:definition>100360 - Disclosure - Fair Value Measurements (Financial Assets and Liabilities Measured at Fair Value on Recurring Basis) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureFairValueMeasurementsNarrativeDetails" id="DisclosureFairValueMeasurementsNarrativeDetails">
        <link:definition>100370 - Disclosure - Fair Value Measurements (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureSupplementalInformationNarrativeDetails" id="DisclosureSupplementalInformationNarrativeDetails">
        <link:definition>100380 - Disclosure - Supplemental Information (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureCommitmentsAndContingenciesNarrativeDetails" id="DisclosureCommitmentsAndContingenciesNarrativeDetails">
        <link:definition>100390 - Disclosure - Commitments and Contingencies (Narrative) (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 roleURI="http://www.paychex.com/20221130/taxonomy/role/DisclosureIncomeTaxesNarrativeDetails" id="DisclosureIncomeTaxesNarrativeDetails">
        <link:definition>100400 - Disclosure - Income Taxes (Narrative) (Details)</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_FundsHeldForClientsAndCorporateInvestmentsAbstract" name="FundsHeldForClientsAndCorporateInvestmentsAbstract" type="xbrli:stringItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_SupplementalInformationAbstract" name="SupplementalInformationAbstract" type="xbrli:stringItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_AccountsNotesAndLoansReceivableGrossCurrent" name="AccountsNotesAndLoansReceivableGrossCurrent" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AccruedWorksiteEmployeeCompensationAndRelatedItems" name="AccruedWorksiteEmployeeCompensationAndRelatedItems" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_AdvanceCollectionsCurrent" name="AdvanceCollectionsCurrent" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterFiveYearsAmortizedCostBasis" name="AvailableForSaleSecuritiesDebtMaturitiesAfterFiveYearsAmortizedCostBasis" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterFiveYearsFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesAfterFiveYearsFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterYearOneThroughYearThreeAmortizedCostBasis" name="AvailableForSaleSecuritiesDebtMaturitiesAfterYearOneThroughYearThreeAmortizedCostBasis" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterYearOneThroughYearThreeFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesAfterYearOneThroughYearThreeFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterYearThreeThroughYearFiveAmortizedCostBasis" name="AvailableForSaleSecuritiesDebtMaturitiesAfterYearThreeThroughYearFiveAmortizedCostBasis" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesAfterYearThreeThroughYearFiveFairValue" name="AvailableForSaleSecuritiesDebtMaturitiesAfterYearThreeThroughYearFiveFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesDebtMaturitiesTerm" name="AvailableForSaleSecuritiesDebtMaturitiesTerm" type="xbrli:durationItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_AvailableForSaleSecuritiesInUnrealizedLossPositionsPercentage" name="AvailableForSaleSecuritiesInUnrealizedLossPositionsPercentage" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false"/>
  <xsd:element id="payx_CapitalizedContractCost" name="CapitalizedContractCost" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_ClientFundObligations" name="ClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_ConcentrationRiskNumberOfClient" name="ConcentrationRiskNumberOfClient" type="xbrli:integerItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_ContractWithCustomerLiabilityAdditions" name="ContractWithCustomerLiabilityAdditions" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_CurrentAssetsBeforeFundsHeldForClients" name="CurrentAssetsBeforeFundsHeldForClients" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_CurrentLiabilitiesBeforeClientFundObligations" name="CurrentLiabilitiesBeforeClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_CustomerContractTerminationNoticeDays" name="CustomerContractTerminationNoticeDays" type="xbrli:durationItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_DirectPassThroughCostGuaranteedCostBenefitPlans" name="DirectPassThroughCostGuaranteedCostBenefitPlans" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_DirectPassThroughCostPayrollWagesAndTaxesIncludingFederalAndStateUnemploymentInsurance" name="DirectPassThroughCostPayrollWagesAndTaxesIncludingFederalAndStateUnemploymentInsurance" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_DirectPassThroughCostStateUnemploymentInsurance" name="DirectPassThroughCostStateUnemploymentInsurance" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_EquityActivityRelatedToStockBasedAwards" name="EquityActivityRelatedToStockBasedAwards" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsAmortizedCost" name="FundsHeldForClientsAndCorporateInvestmentsAmortizedCost" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsFairValue" name="FundsHeldForClientsAndCorporateInvestmentsFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedGains" name="FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedGains" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedLosses" name="FundsHeldForClientsAndCorporateInvestmentsGrossUnrealizedLosses" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsAmortizedCost" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsAmortizedCost" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsFairValue" name="FundsHeldForClientsMoneyMarketSecuritiesAndOtherCashEquivalentsFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_IncreaseDecreaseInOperatingLeaseRightOfUseAssetsAndLiabilitiesNet" name="IncreaseDecreaseInOperatingLeaseRightOfUseAssetsAndLiabilitiesNet" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_IndividualClaimsLiabilityWorkersCompensationInsurance" name="IndividualClaimsLiabilityWorkersCompensationInsurance" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_MaximumIndividualClaimsLiabilityHealthInsurance" name="MaximumIndividualClaimsLiabilityHealthInsurance" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_MaximumIndividualClaimsLiabilityWorkersCompensationInsurance" name="MaximumIndividualClaimsLiabilityWorkersCompensationInsurance" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_NetChangeInClientFundObligations" name="NetChangeInClientFundObligations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_OtherSecuritiesAmortizedCost" name="OtherSecuritiesAmortizedCost" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_OtherSecuritiesFairValue" name="OtherSecuritiesFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_OtherSecuritiesGrossUnrealizedGains" name="OtherSecuritiesGrossUnrealizedGains" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_OtherSecuritiesGrossUnrealizedLosses" name="OtherSecuritiesGrossUnrealizedLosses" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_RestrictedCashAndRestrictedCashEquivalentsIncludedInFundsHeldForClients" name="RestrictedCashAndRestrictedCashEquivalentsIncludedInFundsHeldForClients" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="instant" nillable="true" abstract="false" xbrli:balance="debit"/>
  <xsd:element id="payx_RevenuePerformanceObligationsTimingYears" name="RevenuePerformanceObligationsTimingYears" type="xbrli:durationItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_StockIssuedDuringPeriodValueShareBasedCompensation1" name="StockIssuedDuringPeriodValueShareBasedCompensation1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false" xbrli:balance="credit"/>
  <xsd:element id="payx_AccountingPoliciesLineItems" name="AccountingPoliciesLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_ServiceRevenueLineItems" name="ServiceRevenueLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_AccountsAndUnbilledReceivablesMember" name="AccountsAndUnbilledReceivablesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_AuthorizedInJuly2021Member" name="AuthorizedInJuly2021Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_AuthorizedInMay2019Member" name="AuthorizedInMay2019Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_CostsToFulfillContractMember" name="CostsToFulfillContractMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_CostsToObtainContractMember" name="CostsToObtainContractMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_JpmFiveHundredMillionCreditFacilityMember" name="JpmFiveHundredMillionCreditFacilityMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_JpmOneBillionCreditFacilityMember" name="JpmOneBillionCreditFacilityMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_JpMorganChaseBankNaMember" name="JpMorganChaseBankNaMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_JpmSevenHundredFiftyMillionCreditFacilityMember" name="JpmSevenHundredFiftyMillionCreditFacilityMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_ManagementSolutionsMember" name="ManagementSolutionsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_PeoAggregateClaimsExceeding1.0mMember" name="PeoAggregateClaimsExceeding1.0mMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_PeoAndInsuranceSolutionsMember" name="PeoAndInsuranceSolutionsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_PeoMember" name="PeoMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_SeriesBSeniorNotesMember" name="SeriesBSeniorNotesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_SeriesSeniorNotesMember" name="SeriesSeniorNotesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_AccountingPoliciesTable" name="AccountingPoliciesTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_ServiceRevenueTable" name="ServiceRevenueTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" xbrli:periodType="duration" nillable="true" abstract="true"/>
  <xsd:element id="payx_ClassificationOfInvestmentsOnConsolidatedBalanceSheetsTableTextBlock" name="ClassificationOfInvestmentsOnConsolidatedBalanceSheetsTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_ComponentsOfFundsHeldForClientsAndCorporateInvestmentsTableTextBlock" name="ComponentsOfFundsHeldForClientsAndCorporateInvestmentsTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_FundsHeldForClientsAndCorporateInvestmentsDisclosureTextBlock" name="FundsHeldForClientsAndCorporateInvestmentsDisclosureTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_PassThroughCostsNettedWithinRevenueTableTextBlock" name="PassThroughCostsNettedWithinRevenueTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
  <xsd:element id="payx_SupplementalInformationTextBlock" name="SupplementalInformationTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" xbrli:periodType="duration" nillable="true" abstract="false"/>
</xsd:schema>
