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

<!--XBRL Document Created with the Workiva Platform-->
<!--Copyright 2026 Workiva-->
<!--r:019db0ac-d657-73b3-939f-950e17f21085,g:f772eb96-7601-4d25-90cc-1105fed9d52d-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:hrth="http://www.hartehanks.com/20260331" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2024-01-31" attributeFormDefault="unqualified" elementFormDefault="qualified" targetNamespace="http://www.hartehanks.com/20260331">
  <xs:import namespace="http://fasb.org/srt/2025" schemaLocation="https://xbrl.fasb.org/srt/2025/elts/srt-2025.xsd"/>
  <xs:import namespace="http://fasb.org/us-gaap/2025" schemaLocation="https://xbrl.fasb.org/us-gaap/2025/elts/us-gaap-2025.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.sec.gov/dei/2025" schemaLocation="https://xbrl.sec.gov/dei/2025/dei-2025.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/ecd/2025" schemaLocation="https://xbrl.sec.gov/ecd/2025/ecd-2025.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="hrth-20260331_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="hrth-20260331_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="hrth-20260331_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="hrth-20260331_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple"/>
      <link:roleType id="CoverPage" roleURI="http://www.hartehanks.com/role/CoverPage">
        <link:definition>0000001 - Document - Cover Page</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="CondensedConsolidatedBalanceSheets" roleURI="http://www.hartehanks.com/role/CondensedConsolidatedBalanceSheets">
        <link:definition>9952151 - Statement - Condensed Consolidated Balance Sheets</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CondensedConsolidatedBalanceSheetsParenthetical" roleURI="http://www.hartehanks.com/role/CondensedConsolidatedBalanceSheetsParenthetical">
        <link:definition>9952152 - Statement - Condensed Consolidated Balance Sheets (Parenthetical)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CondensedConsolidatedStatementsofComprehensiveLossUnaudited" roleURI="http://www.hartehanks.com/role/CondensedConsolidatedStatementsofComprehensiveLossUnaudited">
        <link:definition>9952153 - Statement - Condensed Consolidated Statements of Comprehensive Loss (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="CondensedConsolidatedStatementsofChangesinStockholdersEquityUnaudited" roleURI="http://www.hartehanks.com/role/CondensedConsolidatedStatementsofChangesinStockholdersEquityUnaudited">
        <link:definition>9952154 - Statement - Condensed Consolidated Statements of Changes in Stockholders' 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="CondensedConsolidatedStatementsofCashFlowsUnaudited" roleURI="http://www.hartehanks.com/role/CondensedConsolidatedStatementsofCashFlowsUnaudited">
        <link:definition>9952155 - Statement - Condensed 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="OverviewandSignificantAccountingPolicies" roleURI="http://www.hartehanks.com/role/OverviewandSignificantAccountingPolicies">
        <link:definition>9952156 - Disclosure - Overview and Significant Accounting Policies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RecentAccountingPronouncements" roleURI="http://www.hartehanks.com/role/RecentAccountingPronouncements">
        <link:definition>9952157 - Disclosure - Recent 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="RevenuefromContractswithCustomers" roleURI="http://www.hartehanks.com/role/RevenuefromContractswithCustomers">
        <link:definition>9952158 - Disclosure - Revenue from Contracts with Customers</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="Leases" roleURI="http://www.hartehanks.com/role/Leases">
        <link:definition>9952159 - Disclosure - Leases</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="ShareRepurchaseProgram" roleURI="http://www.hartehanks.com/role/ShareRepurchaseProgram">
        <link:definition>9952160 - Disclosure - Share Repurchase Program</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="CreditFacility" roleURI="http://www.hartehanks.com/role/CreditFacility">
        <link:definition>9952161 - Disclosure - Credit Facility</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="StockBasedCompensation" roleURI="http://www.hartehanks.com/role/StockBasedCompensation">
        <link:definition>9952162 - Disclosure - Stock-Based Compensation</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="EmployeeBenefitPlans" roleURI="http://www.hartehanks.com/role/EmployeeBenefitPlans">
        <link:definition>9952163 - Disclosure - Employee Benefit Plans</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxes" roleURI="http://www.hartehanks.com/role/IncomeTaxes">
        <link:definition>9952164 - 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="LossPerShare" roleURI="http://www.hartehanks.com/role/LossPerShare">
        <link:definition>9952165 - Disclosure - Loss 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="ComprehensiveIncomeLoss" roleURI="http://www.hartehanks.com/role/ComprehensiveIncomeLoss">
        <link:definition>9952166 - Disclosure - Comprehensive Income (Loss)</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="LitigationandContingencies" roleURI="http://www.hartehanks.com/role/LitigationandContingencies">
        <link:definition>9952167 - Disclosure - Litigation 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="RestructuringActivities" roleURI="http://www.hartehanks.com/role/RestructuringActivities">
        <link:definition>9952168 - Disclosure - Restructuring Activities</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="SegmentReporting" roleURI="http://www.hartehanks.com/role/SegmentReporting">
        <link:definition>9952169 - Disclosure - Segment Reporting</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="OverviewandSignificantAccountingPoliciesPolicies" roleURI="http://www.hartehanks.com/role/OverviewandSignificantAccountingPoliciesPolicies">
        <link:definition>9955511 - Disclosure - Overview and Significant Accounting Policies (Policies)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RevenuefromContractswithCustomersTables" roleURI="http://www.hartehanks.com/role/RevenuefromContractswithCustomersTables">
        <link:definition>9955512 - Disclosure - Revenue from Contracts with Customers (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="LeasesTables" roleURI="http://www.hartehanks.com/role/LeasesTables">
        <link:definition>9955513 - Disclosure - Leases (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="EmployeeBenefitPlansTables" roleURI="http://www.hartehanks.com/role/EmployeeBenefitPlansTables">
        <link:definition>9955514 - Disclosure - Employee Benefit Plans (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="LossPerShareTables" roleURI="http://www.hartehanks.com/role/LossPerShareTables">
        <link:definition>9955515 - Disclosure - Loss 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="ComprehensiveIncomeLossTables" roleURI="http://www.hartehanks.com/role/ComprehensiveIncomeLossTables">
        <link:definition>9955516 - Disclosure - Comprehensive Income (Loss) (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="RestructuringActivitiesTables" roleURI="http://www.hartehanks.com/role/RestructuringActivitiesTables">
        <link:definition>9955517 - Disclosure - Restructuring Activities (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="SegmentReportingTables" roleURI="http://www.hartehanks.com/role/SegmentReportingTables">
        <link:definition>9955518 - Disclosure - Segment Reporting (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="OverviewandSignificantAccountingPoliciesDetails" roleURI="http://www.hartehanks.com/role/OverviewandSignificantAccountingPoliciesDetails">
        <link:definition>9955519 - Disclosure - Overview and Significant Accounting Policies (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RevenuefromContractswithCustomersScheduleofDisaggregationofRevenueDetails" roleURI="http://www.hartehanks.com/role/RevenuefromContractswithCustomersScheduleofDisaggregationofRevenueDetails">
        <link:definition>9955520 - Disclosure - Revenue from Contracts with Customers - Schedule of Disaggregation of 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 id="RevenuefromContractswithCustomersNarrativeDetails" roleURI="http://www.hartehanks.com/role/RevenuefromContractswithCustomersNarrativeDetails">
        <link:definition>9955521 - Disclosure - Revenue from Contracts with Customers - 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 id="RevenuefromContractswithCustomersScheduleofContractBalancesDetails" roleURI="http://www.hartehanks.com/role/RevenuefromContractswithCustomersScheduleofContractBalancesDetails">
        <link:definition>9955522 - Disclosure - Revenue from Contracts with Customers - Schedule of Contract Balances (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="LeasesNarrativeDetails" roleURI="http://www.hartehanks.com/role/LeasesNarrativeDetails">
        <link:definition>9955523 - Disclosure - Leases - 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 id="LeasesSupplementalBalanceSheetInformationDetails" roleURI="http://www.hartehanks.com/role/LeasesSupplementalBalanceSheetInformationDetails">
        <link:definition>9955524 - Disclosure - Leases - Supplemental Balance Sheet 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="LeasesSupplementalBalanceSheetInformationDetails_1" roleURI="http://www.hartehanks.com/role/LeasesSupplementalBalanceSheetInformationDetails_1">
        <link:definition>9955524 - Disclosure - Leases - Supplemental Balance Sheet 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="LeasesComponentsofLeaseExpenseDetails" roleURI="http://www.hartehanks.com/role/LeasesComponentsofLeaseExpenseDetails">
        <link:definition>9955525 - Disclosure - Leases - Components of Lease 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="LeasesMaturitiesofFinanceandOperatingLeaseLiabilitiesDetails" roleURI="http://www.hartehanks.com/role/LeasesMaturitiesofFinanceandOperatingLeaseLiabilitiesDetails">
        <link:definition>9955526 - Disclosure - Leases - Maturities of Finance and Operating Lease Liabilities (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="LeasesMaturitiesofFinanceandOperatingLeaseLiabilitiesDetails_1" roleURI="http://www.hartehanks.com/role/LeasesMaturitiesofFinanceandOperatingLeaseLiabilitiesDetails_1">
        <link:definition>9955526 - Disclosure - Leases - Maturities of Finance and Operating Lease Liabilities (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="ShareRepurchaseProgramDetails" roleURI="http://www.hartehanks.com/role/ShareRepurchaseProgramDetails">
        <link:definition>9955527 - Disclosure - Share Repurchase Program (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="CreditFacilityDetails" roleURI="http://www.hartehanks.com/role/CreditFacilityDetails">
        <link:definition>9955528 - Disclosure - Credit Facility (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="StockBasedCompensationDetails" roleURI="http://www.hartehanks.com/role/StockBasedCompensationDetails">
        <link:definition>9955529 - Disclosure - Stock-Based Compensation (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="EmployeeBenefitPlansNarrativeDetails" roleURI="http://www.hartehanks.com/role/EmployeeBenefitPlansNarrativeDetails">
        <link:definition>9955530 - Disclosure - Employee Benefit Plans - 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 id="EmployeeBenefitPlansNetPeriodofNetPeriodicCostDetails" roleURI="http://www.hartehanks.com/role/EmployeeBenefitPlansNetPeriodofNetPeriodicCostDetails">
        <link:definition>9955531 - Disclosure - Employee Benefit Plans - Net Period of Net Periodic Cost (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.hartehanks.com/role/IncomeTaxesDetails">
        <link:definition>9955532 - 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="LossPerShareReconciliationsofBasicandDilutedEPSDetails" roleURI="http://www.hartehanks.com/role/LossPerShareReconciliationsofBasicandDilutedEPSDetails">
        <link:definition>9955533 - Disclosure - Loss Per Share - Reconciliations of Basic and Diluted EPS (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="LossPerShareNarrativeDetails" roleURI="http://www.hartehanks.com/role/LossPerShareNarrativeDetails">
        <link:definition>9955534 - Disclosure - Loss Per Share - 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 id="ComprehensiveIncomeLossDetails" roleURI="http://www.hartehanks.com/role/ComprehensiveIncomeLossDetails">
        <link:definition>9955535 - Disclosure - Comprehensive Income (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="RestructuringActivitiesNarrativeDetails" roleURI="http://www.hartehanks.com/role/RestructuringActivitiesNarrativeDetails">
        <link:definition>9955536 - Disclosure - Restructuring Activities - 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 id="RestructuringActivitiesRestructuringExpenseDetails" roleURI="http://www.hartehanks.com/role/RestructuringActivitiesRestructuringExpenseDetails">
        <link:definition>9955537 - Disclosure - Restructuring Activities - Restructuring 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="RestructuringActivitiesChangesinLiabilitiesDetails" roleURI="http://www.hartehanks.com/role/RestructuringActivitiesChangesinLiabilitiesDetails">
        <link:definition>9955538 - Disclosure - Restructuring Activities - Changes in Liabilities (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="SegmentReportingNarrativeDetails" roleURI="http://www.hartehanks.com/role/SegmentReportingNarrativeDetails">
        <link:definition>9955539 - Disclosure - Segment Reporting - 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 id="SegmentReportingFinancialInformationbySegmentDetails" roleURI="http://www.hartehanks.com/role/SegmentReportingFinancialInformationbySegmentDetails">
        <link:definition>9955540 - Disclosure - Segment Reporting - Financial Information by Segment (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="hrth_PrepaidIncomeTaxesAndIncomeTaxReceivableCurrent" abstract="false" name="PrepaidIncomeTaxesAndIncomeTaxReceivableCurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_CustomerPostageAndProgramDepositsCurrent" abstract="false" name="CustomerPostageAndProgramDepositsCurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_OperatingAndFinanceLeaseLiabilityCurrent" abstract="false" name="OperatingAndFinanceLeaseLiabilityCurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_OperatingAndFinanceLeaseLiabilityNoncurrent" abstract="false" name="OperatingAndFinanceLeaseLiabilityNoncurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_IncreaseDecreaseInCustomerPostageAndProgramDeposits" abstract="false" name="IncreaseDecreaseInCustomerPostageAndProgramDeposits" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_FinanceLeasePaymentsIncludingShortTermLeases" abstract="false" name="FinanceLeasePaymentsIncludingShortTermLeases" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_ProceedsFromPaymentsForIssuanceOfTreasuryStock" abstract="false" name="ProceedsFromPaymentsForIssuanceOfTreasuryStock" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_CashReceivedForInterest" abstract="false" name="CashReceivedForInterest" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_AccountingPrinciplesPolicyTextBlock" abstract="false" name="AccountingPrinciplesPolicyTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="hrth_PresentationOfOperatingExpenseInConsolidatedStatementsOfComprehensiveIncomePolicyTextBlock" abstract="false" name="PresentationOfOperatingExpenseInConsolidatedStatementsOfComprehensiveIncomePolicyTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="hrth_LesseeLeasesSupplementalBalanceSheetInformationTableTextBlock" abstract="false" name="LesseeLeasesSupplementalBalanceSheetInformationTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="hrth_LeaseLiabilityMaturityTableTextBlock" abstract="false" name="LeaseLiabilityMaturityTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="hrth_RevenueSolutionsMember" abstract="true" name="RevenueSolutionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_CustomerCareMember" abstract="true" name="CustomerCareMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_FulfillmentAndLogisticsServicesMember" abstract="true" name="FulfillmentAndLogisticsServicesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_LesseeLeaseRemainingLeaseTerm" abstract="false" name="LesseeLeaseRemainingLeaseTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="hrth_LesseeLeaseRenewalTerm" abstract="false" name="LesseeLeaseRenewalTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="hrth_FinanceLeaseRightOfUseAssetAccumulatedDepreciation" abstract="false" name="FinanceLeaseRightOfUseAssetAccumulatedDepreciation" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_OperatingAndFinanceLeaseRightOfUseAsset" abstract="false" name="OperatingAndFinanceLeaseRightOfUseAsset" nillable="true" xbrli:periodType="instant" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_OperatingAndFinanceLeaseLiability" abstract="false" name="OperatingAndFinanceLeaseLiability" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_FinanceLeaseCost" abstract="false" name="FinanceLeaseCost" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_CashFlowLesseeAbstract" abstract="true" name="CashFlowLesseeAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="hrth_WeightedAverageRemainingLeaseTermAbstract" abstract="true" name="WeightedAverageRemainingLeaseTermAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="hrth_LeasesWeightedAverageDiscountRateAbstract" abstract="true" name="LeasesWeightedAverageDiscountRateAbstract" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="hrth_LesseeOperatingLeaseLiabilityToBePaidAfterYearFour" abstract="false" name="LesseeOperatingLeaseLiabilityToBePaidAfterYearFour" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_FinanceLeaseLiabilityToBePaidAfterYearFour" abstract="false" name="FinanceLeaseLiabilityToBePaidAfterYearFour" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_CreditFacilityMember" abstract="true" name="CreditFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_NewCreditFacilityMember" abstract="true" name="NewCreditFacilityMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_TexasCapitalBankMember" abstract="true" name="TexasCapitalBankMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_DebtInstrumentRenewalTerm" abstract="false" name="DebtInstrumentRenewalTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="hrth_LineOfCreditFacilityAccordionFeatureIncreaseLimit" abstract="false" name="LineOfCreditFacilityAccordionFeatureIncreaseLimit" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_QualifiedPlanIIMember" abstract="true" name="QualifiedPlanIIMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_DefinedBenefitPlanNumberOfPlans" abstract="false" name="DefinedBenefitPlanNumberOfPlans" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="hrth_RestructuringAndRelatedCostCostReductions" abstract="false" name="RestructuringAndRelatedCostCostReductions" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_ConsultingAndEmployeeExpenseMember" abstract="true" name="ConsultingAndEmployeeExpenseMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="hrth_ContributionMargin" abstract="false" name="ContributionMargin" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="hrth_EBITDA" abstract="false" name="EBITDA" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
</xs:schema>
