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

<!--XBRL Document Created with the Workiva Platform-->
<!--Copyright 2026 Workiva-->
<!--r:019e40b0-bf20-74e1-b393-6ab5dd86f79b,g:4628b362-fe94-4496-9d7d-dea98b072e90-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:dlx="http://www.deluxe.com/20260630" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2024-01-31" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.deluxe.com/20260630">
  <xs:import namespace="http://fasb.org/srt/2026" schemaLocation="https://xbrl.fasb.org/srt/2026/elts/srt-2026.xsd"/>
  <xs:import namespace="http://fasb.org/us-gaap/2026" schemaLocation="https://xbrl.fasb.org/us-gaap/2026/elts/us-gaap-2026.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/2024-01-31" schemaLocation="https://www.xbrl.org/dtr/type/2024-01-31/types.xsd"/>
  <xs:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/dei/2026" schemaLocation="https://xbrl.sec.gov/dei/2026/dei-2026.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/ecd/2026" schemaLocation="https://xbrl.sec.gov/ecd/2026/ecd-2026.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/naics/2026" schemaLocation="https://xbrl.sec.gov/naics/2026/naics-2026.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-20260630_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-20260630_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" 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-20260630_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-20260630_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" 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>9952151 - 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>9952152 - 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>9952153 - 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>9952154 - 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>9952155 - 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>9952156 - 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>9952157 - 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>9952158 - 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>9952159 - 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="Shareholdersequity" roleURI="http://www.deluxe.com/role/Shareholdersequity">
        <link:definition>9952160 - 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="Earningspershare" roleURI="http://www.deluxe.com/role/Earningspershare">
        <link:definition>9952161 - 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="Acquisitionanddivestitures" roleURI="http://www.deluxe.com/role/Acquisitionanddivestitures">
        <link:definition>9952162 - Disclosure - Acquisition and 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="Fairvaluemeasurements" roleURI="http://www.deluxe.com/role/Fairvaluemeasurements">
        <link:definition>9952163 - 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>9952164 - 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="Incometaxes" roleURI="http://www.deluxe.com/role/Incometaxes">
        <link:definition>9952165 - 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="Postretirementbenefits" roleURI="http://www.deluxe.com/role/Postretirementbenefits">
        <link:definition>9952166 - 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>9952167 - 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>9952168 - 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="Businesssegmentinformation" roleURI="http://www.deluxe.com/role/Businesssegmentinformation">
        <link:definition>9952169 - 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="Subsequentevent" roleURI="http://www.deluxe.com/role/Subsequentevent">
        <link:definition>9952170 - Disclosure - Subsequent event</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>9955511 - 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="NewaccountingpronouncementsPolicies" roleURI="http://www.deluxe.com/role/NewaccountingpronouncementsPolicies">
        <link:definition>9955512 - Disclosure - New accounting pronouncements (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>9955513 - 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="ShareholdersequityTables" roleURI="http://www.deluxe.com/role/ShareholdersequityTables">
        <link:definition>9955514 - Disclosure - Shareholders' equity (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>9955515 - 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="AcquisitionanddivestituresTables" roleURI="http://www.deluxe.com/role/AcquisitionanddivestituresTables">
        <link:definition>9955516 - Disclosure - Acquisition and divestitures (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>9955517 - 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>9955518 - 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>9955519 - 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>9955520 - 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>9955521 - 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>9955522 - 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>9955523 - 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="SupplementalbalancesheetandcashflowinformationrevenueinexcessofbillingsDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationrevenueinexcessofbillingsDetails">
        <link:definition>9955524 - 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="SupplementalbalancesheetandcashflowinformationgoodwillDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationgoodwillDetails">
        <link:definition>9955525 - 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="SupplementalbalancesheetandcashflowinformationintangiblesDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationintangiblesDetails">
        <link:definition>9955526 - 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="SupplementalbalancesheetandcashflowinformationothernoncurrentassetsDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationothernoncurrentassetsDetails">
        <link:definition>9955527 - 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="SupplementalbalancesheetandcashflowinformationaccruedliabilitiessupplementalcashflowinformationDetails" roleURI="http://www.deluxe.com/role/SupplementalbalancesheetandcashflowinformationaccruedliabilitiessupplementalcashflowinformationDetails">
        <link:definition>9955528 - Disclosure - Supplemental balance sheet and cash flow information (accrued liabilities, 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="ShareholdersequityaccumulatedothercomprehensivelossDetails" roleURI="http://www.deluxe.com/role/ShareholdersequityaccumulatedothercomprehensivelossDetails">
        <link:definition>9955529 - Disclosure - Shareholders' equity (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="ShareholdersequityreclassificationadjustmentsDetails" roleURI="http://www.deluxe.com/role/ShareholdersequityreclassificationadjustmentsDetails">
        <link:definition>9955530 - Disclosure - Shareholders' equity (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="EarningspershareDetails" roleURI="http://www.deluxe.com/role/EarningspershareDetails">
        <link:definition>9955531 - 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="AcquisitionanddivestituresDetails" roleURI="http://www.deluxe.com/role/AcquisitionanddivestituresDetails">
        <link:definition>9955532 - Disclosure - Acquisition and 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="FairvaluemeasurementsDetails" roleURI="http://www.deluxe.com/role/FairvaluemeasurementsDetails">
        <link:definition>9955533 - 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>9955534 - 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>9955535 - 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="IncometaxesDetails" roleURI="http://www.deluxe.com/role/IncometaxesDetails">
        <link:definition>9955536 - 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="PostretirementbenefitsDetails" roleURI="http://www.deluxe.com/role/PostretirementbenefitsDetails">
        <link:definition>9955537 - 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>9955538 - 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>9955538 - 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>9955539 - 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="BusinesssegmentinformationDetails" roleURI="http://www.deluxe.com/role/BusinesssegmentinformationDetails">
        <link:definition>9955540 - 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>9955541 - 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>
      <link:roleType id="SubsequenteventDetails" roleURI="http://www.deluxe.com/role/SubsequenteventDetails">
        <link:definition>9955542 - Disclosure - Subsequent event (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_Revenueinexcessofbillingscurrent" abstract="false" name="Revenueinexcessofbillingscurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <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_StockIssuedDuringPeriodValueNetOfTaxWithheld" abstract="false" name="StockIssuedDuringPeriodValueNetOfTaxWithheld" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_StockIssuedDuringPeriodSharesNetOfTaxWithheld" abstract="false" name="StockIssuedDuringPeriodSharesNetOfTaxWithheld" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:sharesItemType"/>
  <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_Prepaidproductdiscountpayments" abstract="false" name="Prepaidproductdiscountpayments" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_HoldbackPaymentsToAcquireAssets" abstract="false" name="HoldbackPaymentsToAcquireAssets" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_NetChangeInSettlementProcessingLiabilities" abstract="false" name="NetChangeInSettlementProcessingLiabilities" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_AcquisitionAndDivestitures" abstract="false" name="AcquisitionAndDivestitures" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <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_MerchantServicesMember" abstract="true" name="MerchantServicesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_B2BPaymentsMember" abstract="true" name="B2BPaymentsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <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_PrintMember" abstract="true" name="PrintMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <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_ResidualCommissionBuyOutMember" abstract="true" name="ResidualCommissionBuyOutMember" 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_CurrentPortionOfLongTermReceivableOriginatedInCurrentFiscalYear" abstract="false" name="CurrentPortionOfLongTermReceivableOriginatedInCurrentFiscalYear" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_BalanceSheetRelatedDisclosuresTableTable" abstract="true" name="BalanceSheetRelatedDisclosuresTableTable" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType"/>
  <xs:element id="dlx_BalanceSheetRelatedDisclosureLineItemsLineItems" abstract="true" name="BalanceSheetRelatedDisclosureLineItemsLineItems" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <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_Prepaidproductdiscountliabilitycurrent" abstract="false" name="Prepaidproductdiscountliabilitycurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <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_ConsiderationPayableForAssetPurchases" abstract="false" name="ConsiderationPayableForAssetPurchases" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" 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_RemeasurementOfLiabilityShareBasedAward" abstract="false" name="RemeasurementOfLiabilityShareBasedAward" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_CeleroCommerceMember" abstract="true" name="CeleroCommerceMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_SafeguardSmallBusinessDistributorChannelMember" abstract="true" name="SafeguardSmallBusinessDistributorChannelMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_TotalConsiderationFromSaleOfBusiness" abstract="false" name="TotalConsiderationFromSaleOfBusiness" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_CollectionPeriodForLongTermReceivable" abstract="false" name="CollectionPeriodForLongTermReceivable" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="dlx_NetAssetsDisposed" abstract="false" name="NetAssetsDisposed" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_ProceedsReceivableFromAssetSaleMember" abstract="true" name="ProceedsReceivableFromAssetSaleMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ExternalConsultingAndOtherCostsMember" abstract="true" name="ExternalConsultingAndOtherCostsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_InternallaborMember" abstract="true" name="InternallaborMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_RestructuringChargesCostOfRevenue" abstract="false" name="RestructuringChargesCostOfRevenue" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_RestructuringChargesOperatingExpenses" abstract="false" name="RestructuringChargesOperatingExpenses" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <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_TermLoanFacilityMember" abstract="true" name="TermLoanFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_ARSecuritizationMember" abstract="true" name="ARSecuritizationMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <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_CreditFacilityAgreementMember" abstract="true" name="CreditFacilityAgreementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_AmendedTermLoanFacilityMember" abstract="true" name="AmendedTermLoanFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_AmendedRevolvingCreditFacilityMember" abstract="true" name="AmendedRevolvingCreditFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_AmendedCreditFacilityAgreementMember" abstract="true" name="AmendedCreditFacilityAgreementMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_LineOfCreditFacilityCovenantTotalLeverageCashRequirement" abstract="false" name="LineOfCreditFacilityCovenantTotalLeverageCashRequirement" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_LineOfCreditFacilityCovenantSecuredLeverageCashRequirement" abstract="false" name="LineOfCreditFacilityCovenantSecuredLeverageCashRequirement" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_ConsolidatedTotalLeverageRatio" abstract="false" name="ConsolidatedTotalLeverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_MaximumConsolidatedSecuredLeverageRatio" abstract="false" name="MaximumConsolidatedSecuredLeverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_MinimumInterestCoverageRatio" abstract="false" name="MinimumInterestCoverageRatio" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <xs:element id="dlx_ConsolidatedTotalLeverageRatioLimitingPermittedPayments" abstract="false" name="ConsolidatedTotalLeverageRatioLimitingPermittedPayments" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:pureItemType"/>
  <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_AnnualShareRepurchaseLimitation" abstract="false" name="AnnualShareRepurchaseLimitation" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="dlx_MajorCustomersMemberMember" abstract="true" name="MajorCustomersMemberMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_NumberOfCustomers" abstract="false" name="NumberOfCustomers" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <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_NumberOfReportableSegmentsNotDisclosedFlag" abstract="false" name="NumberOfReportableSegmentsNotDisclosedFlag" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:booleanItemType"/>
  <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_MerchantServicesRevenueMember" abstract="true" name="MerchantServicesRevenueMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <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_TreasurymanagementsolutionsMember" abstract="true" name="TreasurymanagementsolutionsMember" 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_PromotionalSolutionsRevenueMember" abstract="true" name="PromotionalSolutionsRevenueMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_OtherPaymentSolutionsMemberMember" abstract="true" name="OtherPaymentSolutionsMemberMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="dlx_OtherWebBasedSolutionsMember" abstract="true" name="OtherWebBasedSolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
</xs:schema>
