<?xml version="1.0" encoding="UTF-8"?>

<!--XBRL Document Created with the Workiva Platform-->
<!--Copyright 2023 Workiva-->
<!--r:0f40896b-3651-404f-910f-5a9fc55517d6,g:f48395e8-1a97-4adc-a8a0-eb4625c927e2-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:dlx="http://www.deluxe.com/20230630" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2020-01-21" attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.deluxe.com/20230630">
  <xs:import namespace="http://fasb.org/srt/2022" schemaLocation="https://xbrl.fasb.org/srt/2022/elts/srt-2022.xsd"/>
  <xs:import namespace="http://fasb.org/us-gaap/2022" schemaLocation="https://xbrl.fasb.org/us-gaap/2022/elts/us-gaap-2022.xsd"/>
  <xs:import namespace="http://www.w3.org/1999/xlink" schemaLocation="http://www.xbrl.org/2003/xlink-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/2003/linkbase" schemaLocation="http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd"/>
  <xs:import namespace="http://www.xbrl.org/dtr/type/2020-01-21" schemaLocation="https://www.xbrl.org/dtr/type/2020-01-21/types.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/country/2022" schemaLocation="https://xbrl.sec.gov/country/2022/country-2022.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/dei/2022" schemaLocation="https://xbrl.sec.gov/dei/2022/dei-2022.xsd"/>
  <xs:annotation>
    <xs:appinfo>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="dlx-20230630_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="dlx-20230630_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="dlx-20230630_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple"/>
      <link:linkbaseRef xmlns:xlink="http://www.w3.org/1999/xlink" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" xlink:href="dlx-20230630_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:type="simple"/>
      <link:roleType id="Document" roleURI="http://www.deluxe.com/role/Document">
        <link:definition>0000001 - Document - Document</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="CONSOLIDATEDBALANCESHEETSUnaudited" roleURI="http://www.deluxe.com/role/CONSOLIDATEDBALANCESHEETSUnaudited">
        <link:definition>0000002 - Statement - CONSOLIDATED BALANCE SHEETS (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="CONSOLIDATEDBALANCESHEETSUnauditedParentheticals" roleURI="http://www.deluxe.com/role/CONSOLIDATEDBALANCESHEETSUnauditedParentheticals">
        <link:definition>0000003 - Statement - CONSOLIDATED BALANCE SHEETS (Unaudited) (Parentheticals)</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="CONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOMEUnaudited" roleURI="http://www.deluxe.com/role/CONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOMEUnaudited">
        <link:definition>0000004 - Statement - CONSOLIDATED STATEMENTS OF COMPREHENSIVE INCOME (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="CONSOLIDATEDSTATEMENTSOFSHAREHOLDERSEQUITYUnaudited" roleURI="http://www.deluxe.com/role/CONSOLIDATEDSTATEMENTSOFSHAREHOLDERSEQUITYUnaudited">
        <link:definition>0000005 - Statement - CONSOLIDATED STATEMENTS OF SHAREHOLDERS' EQUITY (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="CONSOLIDATEDSTATEMENTSOFSHAREHOLDERSEQUITYUnauditedParentheticals" roleURI="http://www.deluxe.com/role/CONSOLIDATEDSTATEMENTSOFSHAREHOLDERSEQUITYUnauditedParentheticals">
        <link:definition>0000006 - Statement - CONSOLIDATED STATEMENTS OF SHAREHOLDERS' EQUITY (Unaudited) (Parentheticals)</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="CONSOLIDATEDSTATEMENTSOFCASHFLOWSUnaudited" roleURI="http://www.deluxe.com/role/CONSOLIDATEDSTATEMENTSOFCASHFLOWSUnaudited">
        <link:definition>0000007 - Statement - CONSOLIDATED STATEMENTS OF CASH FLOWS (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="Consolidatedfinancialstatements" roleURI="http://www.deluxe.com/role/Consolidatedfinancialstatements">
        <link:definition>0000008 - Disclosure - Consolidated financial statements</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="Newaccountingpronouncements" roleURI="http://www.deluxe.com/role/Newaccountingpronouncements">
        <link:definition>0000009 - Disclosure - New accounting pronouncements</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="Supplementalbalancesheetandcashflowinformation" roleURI="http://www.deluxe.com/role/Supplementalbalancesheetandcashflowinformation">
        <link:definition>0000010 - Disclosure - Supplemental balance sheet and 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="Earningspershare" roleURI="http://www.deluxe.com/role/Earningspershare">
        <link:definition>0000011 - Disclosure - 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="Othercomprehensiveincome" roleURI="http://www.deluxe.com/role/Othercomprehensiveincome">
        <link:definition>0000012 - Disclosure - Other comprehensive income</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="Divestitures" roleURI="http://www.deluxe.com/role/Divestitures">
        <link:definition>0000013 - Disclosure - Divestitures</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="Derivativefinancialinstruments" roleURI="http://www.deluxe.com/role/Derivativefinancialinstruments">
        <link:definition>0000014 - Disclosure - Derivative financial instruments</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.deluxe.com/role/Fairvaluemeasurements">
        <link:definition>0000015 - 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="Restructuringandintegrationexpense" roleURI="http://www.deluxe.com/role/Restructuringandintegrationexpense">
        <link:definition>0000016 - Disclosure - Restructuring and integration expense</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="Incometaxprovision" roleURI="http://www.deluxe.com/role/Incometaxprovision">
        <link:definition>0000017 - Disclosure - Income tax provision</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="Postretirementbenefits" roleURI="http://www.deluxe.com/role/Postretirementbenefits">
        <link:definition>0000018 - Disclosure - Postretirement benefits</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="Debt" roleURI="http://www.deluxe.com/role/Debt">
        <link:definition>0000019 - Disclosure - Debt</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="Othercommitmentsandcontingencies" roleURI="http://www.deluxe.com/role/Othercommitmentsandcontingencies">
        <link:definition>0000020 - Disclosure - Other 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="Shareholdersequity" roleURI="http://www.deluxe.com/role/Shareholdersequity">
        <link:definition>0000021 - Disclosure - Shareholders' 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="Businesssegmentinformation" roleURI="http://www.deluxe.com/role/Businesssegmentinformation">
        <link:definition>0000022 - Disclosure - Business segment 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="ConsolidatedfinancialstatementsPolicies" roleURI="http://www.deluxe.com/role/ConsolidatedfinancialstatementsPolicies">
        <link:definition>0000023 - Disclosure - Consolidated financial statements (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="SupplementalbalancesheetandcashflowinformationTables" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationTables">
        <link:definition>0000024 - Disclosure - Supplemental balance sheet and cash flow information (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="EarningspershareTables" roleURI="http://www.deluxe.com/role/EarningspershareTables">
        <link:definition>0000025 - Disclosure - 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="OthercomprehensiveincomeTables" roleURI="http://www.deluxe.com/role/OthercomprehensiveincomeTables">
        <link:definition>0000026 - Disclosure - 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="DerivativefinancialinstrumentsTables" roleURI="http://www.deluxe.com/role/DerivativefinancialinstrumentsTables">
        <link:definition>0000027 - Disclosure - Derivative financial instruments (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="FairvaluemeasurementsTables" roleURI="http://www.deluxe.com/role/FairvaluemeasurementsTables">
        <link:definition>0000028 - 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="RestructuringandintegrationexpenseTables" roleURI="http://www.deluxe.com/role/RestructuringandintegrationexpenseTables">
        <link:definition>0000029 - Disclosure - Restructuring and integration expense (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="PostretirementbenefitsTables" roleURI="http://www.deluxe.com/role/PostretirementbenefitsTables">
        <link:definition>0000030 - Disclosure - Postretirement benefits (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="DebtTables" roleURI="http://www.deluxe.com/role/DebtTables">
        <link:definition>0000031 - Disclosure - Debt (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="BusinesssegmentinformationTables" roleURI="http://www.deluxe.com/role/BusinesssegmentinformationTables">
        <link:definition>0000032 - Disclosure - Business segment information (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="SupplementalbalancesheetandcashflowinformationtradeaccountsreceivableallowanceforcreditlossesDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationtradeaccountsreceivableallowanceforcreditlossesDetails">
        <link:definition>0000033 - Disclosure - Supplemental balance sheet and cash flow information (trade accounts receivable, allowance for credit losses) (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="SupplementalbalancesheetandcashflowinformationinventoriesandsuppliesDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationinventoriesandsuppliesDetails">
        <link:definition>0000034 - Disclosure - Supplemental balance sheet and cash flow information (inventories and supplies) (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="SupplementalbalancesheetandcashflowinformationavailableforsaledebtsecuritiesDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationavailableforsaledebtsecuritiesDetails">
        <link:definition>0000035 - Disclosure - Supplemental balance sheet and cash flow information (available-for-sale debt 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 id="SupplementalbalancesheetandcashflowinformationrevenueinexcessofbillingsDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationrevenueinexcessofbillingsDetails">
        <link:definition>0000036 - Disclosure - Supplemental balance sheet and cash flow information (revenue in excess of billings) (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="SupplementalbalancesheetandcashflowinformationintangiblesDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationintangiblesDetails">
        <link:definition>0000037 - Disclosure - Supplemental balance sheet and cash flow information (intangibles) (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="SupplementalbalancesheetandcashflowinformationgoodwillDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationgoodwillDetails">
        <link:definition>0000038 - Disclosure - Supplemental balance sheet and cash flow information (goodwill) (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="SupplementalbalancesheetandcashflowinformationothernoncurrentassetsDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationothernoncurrentassetsDetails">
        <link:definition>0000039 - Disclosure - Supplemental balance sheet and cash flow information (other non-current assets) (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="SupplementalbalancesheetandcashflowinformationotherDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationotherDetails">
        <link:definition>0000040 - Disclosure - Supplemental balance sheet and cash flow information (other) (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="EarningspershareDetails" roleURI="http://www.deluxe.com/role/EarningspershareDetails">
        <link:definition>0000041 - Disclosure - 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="OthercomprehensiveincomereclassificationadjustmentsDetails" roleURI="http://www.deluxe.com/role/OthercomprehensiveincomereclassificationadjustmentsDetails">
        <link:definition>0000042 - Disclosure - Other comprehensive income (reclassification adjustments) (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="OthercomprehensiveincomeaccumulatedothercomprehensivelossDetails" roleURI="http://www.deluxe.com/role/OthercomprehensiveincomeaccumulatedothercomprehensivelossDetails">
        <link:definition>0000043 - Disclosure - Other comprehensive income (accumulated other comprehensive loss) (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="DivestituresDetails" roleURI="http://www.deluxe.com/role/DivestituresDetails">
        <link:definition>0000044 - Disclosure - Divestitures (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="DerivativefinancialinstrumentsDetails" roleURI="http://www.deluxe.com/role/DerivativefinancialinstrumentsDetails">
        <link:definition>0000045 - Disclosure - Derivative financial instruments (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="FairvaluemeasurementsDetails" roleURI="http://www.deluxe.com/role/FairvaluemeasurementsDetails">
        <link:definition>0000046 - 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="RestructuringandintegrationexpenseDetails" roleURI="http://www.deluxe.com/role/RestructuringandintegrationexpenseDetails">
        <link:definition>0000047 - Disclosure - Restructuring and integration expense (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="RestructuringandintegrationexpenseaccrualsDetails" roleURI="http://www.deluxe.com/role/RestructuringandintegrationexpenseaccrualsDetails">
        <link:definition>0000048 - Disclosure - Restructuring and integration expense (accruals) (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="IncometaxprovisionDetails" roleURI="http://www.deluxe.com/role/IncometaxprovisionDetails">
        <link:definition>0000049 - Disclosure - Income tax provision (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="PostretirementbenefitsDetails" roleURI="http://www.deluxe.com/role/PostretirementbenefitsDetails">
        <link:definition>0000050 - Disclosure - Postretirement benefits (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="DebtDetails" roleURI="http://www.deluxe.com/role/DebtDetails">
        <link:definition>0000051 - Disclosure - Debt (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="DebtDetails_1" roleURI="http://www.deluxe.com/role/DebtDetails_1">
        <link:definition>0000051 - Disclosure - Debt (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="OthercommitmentsandcontingenciesDetails" roleURI="http://www.deluxe.com/role/OthercommitmentsandcontingenciesDetails">
        <link:definition>0000052 - Disclosure - Other 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="ShareholdersequityDetails" roleURI="http://www.deluxe.com/role/ShareholdersequityDetails">
        <link:definition>0000053 - Disclosure - Shareholders' equity (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="BusinesssegmentinformationDetails" roleURI="http://www.deluxe.com/role/BusinesssegmentinformationDetails">
        <link:definition>0000054 - Disclosure - Business segment 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="BusinesssegmentinformationdisaggregatedrevenueinformationDetails" roleURI="http://www.deluxe.com/role/BusinesssegmentinformationdisaggregatedrevenueinformationDetails">
        <link:definition>0000055 - Disclosure - Business segment information (disaggregated revenue information) (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xs:appinfo>
  </xs:annotation>
  <xs:element id="dlx_SwinglineSubFacilityMember" abstract="true" name="SwinglineSubFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_BusinessExitActivitiesYearOverYearImpact" abstract="false" name="BusinessExitActivitiesYearOverYearImpact" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:percentItemType"/>
  <xs:element id="dlx_OtherCurrentAndNoncurrentAssetsMember" abstract="true" name="OtherCurrentAndNoncurrentAssetsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Netchangeincustomerfundsobligations" abstract="false" name="Netchangeincustomerfundsobligations" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_OtherCommonSharesRetiredShares" abstract="false" name="OtherCommonSharesRetiredShares" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:sharesItemType"/>
  <xs:element id="dlx_TermLoanFacilityMember" abstract="true" name="TermLoanFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_SoftwareforResaleMember" abstract="true" name="SoftwareforResaleMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_OtherCommonSharesRetiredValue" abstract="false" name="OtherCommonSharesRetiredValue" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_PermittedPayments" abstract="false" name="PermittedPayments" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_Additionstoprepaidproductdiscounts" abstract="false" name="Additionstoprepaidproductdiscounts" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_ReclassificationAdjustmentsAbstract" abstract="true" name="ReclassificationAdjustmentsAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="dlx_InternaluseComputerSoftwareIntangibleAssetMember" abstract="true" name="InternaluseComputerSoftwareIntangibleAssetMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_InterestRateSwapSeptember2022Member" abstract="true" name="InterestRateSwapSeptember2022Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_LancasterCaliforniaFacilityMember" abstract="true" name="LancasterCaliforniaFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Restructuringchargesnet" abstract="false" name="Restructuringchargesnet" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_Prepaidproductdiscountliabilitycurrent" abstract="false" name="Prepaidproductdiscountliabilitycurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_TreasurymanagementsolutionsMember" abstract="true" name="TreasurymanagementsolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_LoansandnotesreceivablefromdistributorsMember" abstract="true" name="LoansandnotesreceivablefromdistributorsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_FundsHeldForCustomersMember" abstract="true" name="FundsHeldForCustomersMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ConsolidatedTotalLeverageRatioLimitingPermittedPayments" abstract="false" name="ConsolidatedTotalLeverageRatioLimitingPermittedPayments" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_PaymentsMember" abstract="true" name="PaymentsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_RestrictedCashFairValueDisclosure" abstract="false" name="RestrictedCashFairValueDisclosure" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_Otherchangesinprepaidproductdiscounts" abstract="false" name="Otherchangesinprepaidproductdiscounts" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_CustomerRebates" abstract="false" name="CustomerRebates" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_ExternalconsultingfeesMember" abstract="true" name="ExternalconsultingfeesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ChecksrevenueMember" abstract="true" name="ChecksrevenueMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_PrepaidproductdiscountsRollForward" abstract="true" name="PrepaidproductdiscountsRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="dlx_RemeasurementOfLiabilityShareBasedAward" abstract="false" name="RemeasurementOfLiabilityShareBasedAward" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_AdjustedEBITDA" abstract="false" name="AdjustedEBITDA" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_PrepaidproductdiscountsAbstract" abstract="true" name="PrepaidproductdiscountsAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="dlx_ScheduleofprepaidproductdiscountsTableTextBlock" abstract="false" name="ScheduleofprepaidproductdiscountsTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="dlx_AustralianWebHostingBusinessMember" abstract="true" name="AustralianWebHostingBusinessMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_FormsandotherproductsMember" abstract="true" name="FormsandotherproductsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Amortizationofprepaidproductdiscounts" abstract="false" name="Amortizationofprepaidproductdiscounts" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_DatadrivenmarketingsolutionsMember" abstract="true" name="DatadrivenmarketingsolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_FundsHeldForCustomersLiability" abstract="false" name="FundsHeldForCustomersLiability" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_TaxImpactOfShareBasedCompensationYearOverYearImpact" abstract="false" name="TaxImpactOfShareBasedCompensationYearOverYearImpact" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:percentItemType"/>
  <xs:element id="dlx_DebtCovenantsTableTextBlock" abstract="false" name="DebtCovenantsTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="dlx_DataSolutionsMember" abstract="true" name="DataSolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ConsolidatedTotalLeverageRatio" abstract="false" name="ConsolidatedTotalLeverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_FinancingReceivableOriginatedFiveYearsBeforeLatestFiscalYear" abstract="false" name="FinancingReceivableOriginatedFiveYearsBeforeLatestFiscalYear" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_CurrentPortionOfLongTermDebtAndLongTermDebtMember" abstract="true" name="CurrentPortionOfLongTermDebtAndLongTermDebtMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_WebandhostedsolutionsMember" abstract="true" name="WebandhostedsolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_InterestRateSwapJune2023Member" abstract="true" name="InterestRateSwapJune2023Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Prepaidproductdiscounts" abstract="false" name="Prepaidproductdiscounts" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_PromotionalSolutionsBusinessExitsMember" abstract="true" name="PromotionalSolutionsBusinessExitsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Prepaidproductdiscountpayments" abstract="false" name="Prepaidproductdiscountpayments" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_InterestRateSwapJuly2019Member" abstract="true" name="InterestRateSwapJuly2019Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_PromotionalSolutionsMember" abstract="true" name="PromotionalSolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_Revenueinexcessofbillingscurrent" abstract="false" name="Revenueinexcessofbillingscurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_MarketingandpromotionalsolutionsMember" abstract="true" name="MarketingandpromotionalsolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_FinancingReceivableAllowanceForCreditLossesOtherChange" abstract="false" name="FinancingReceivableAllowanceForCreditLossesOtherChange" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_OnetotwointernalgradememberMember" abstract="true" name="OnetotwointernalgradememberMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_NorthAmericanWebHostingAndLogoDesignBusinessesMember" abstract="true" name="NorthAmericanWebHostingAndLogoDesignBusinessesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_RestructuringOperatingExpense" abstract="false" name="RestructuringOperatingExpense" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_InterestRateSwapMarch2023Member" abstract="true" name="InterestRateSwapMarch2023Member" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ChecksMember" abstract="true" name="ChecksMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_LongTermDebtMaturityAfterYearFour" abstract="false" name="LongTermDebtMaturityAfterYearFour" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_MaximumConsolidatedSecuredLeverageRatio" abstract="false" name="MaximumConsolidatedSecuredLeverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_PaymentsForCloudComputingArrangementImplementationCosts" abstract="false" name="PaymentsForCloudComputingArrangementImplementationCosts" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_MerchantServicesAndOtherPaymentsSolutionsMember" abstract="true" name="MerchantServicesAndOtherPaymentsSolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ThreetofourinternalgradeMember" abstract="true" name="ThreetofourinternalgradeMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_AccruedWagesAndPayrollLiabilities" abstract="false" name="AccruedWagesAndPayrollLiabilities" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_LitigationSettlementPeriod" abstract="false" name="LitigationSettlementPeriod" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="dlx_ReturnToProvisionAdjustmentsYearOverYearImpact" abstract="false" name="ReturnToProvisionAdjustmentsYearOverYearImpact" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:percentItemType"/>
  <xs:element id="dlx_MinimumInterestCoverageRatio" abstract="false" name="MinimumInterestCoverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_InternallaborMember" abstract="true" name="InternallaborMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
</xs:schema>
