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

<!--XBRL Document Created with the Workiva Platform-->
<!--Copyright 2026 Workiva-->
<!--r:019c9ace-ce61-7c3d-a4a6-1fbc228b7515,g:a73e06d0-2728-464c-83cb-2873b4818b3d-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:spok="http://www.spok.com/20260331" 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.spok.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.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd"/>
  <xs:import namespace="http://xbrl.sec.gov/country/2025" schemaLocation="https://xbrl.sec.gov/country/2025/country-2025.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="spok-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="spok-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="spok-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="spok-20260331_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:type="simple"/>
      <link:roleType id="Cover" roleURI="http://www.spok.com/role/Cover">
        <link:definition>0000001 - Document - Cover</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.spok.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="CONDENSEDCONSOLIDATEDSTATEMENTSOFOPERATIONS" roleURI="http://www.spok.com/role/CONDENSEDCONSOLIDATEDSTATEMENTSOFOPERATIONS">
        <link:definition>9952152 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS</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="CONDENSEDCONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOME" roleURI="http://www.spok.com/role/CONDENSEDCONSOLIDATEDSTATEMENTSOFCOMPREHENSIVEINCOME">
        <link:definition>9952153 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF 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="CONDENSEDCONSOLIDATEDSTATEMENTSOFSTOCKHOLDERSEQUITY" roleURI="http://www.spok.com/role/CONDENSEDCONSOLIDATEDSTATEMENTSOFSTOCKHOLDERSEQUITY">
        <link:definition>9952154 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF STOCKHOLDERS&#8217; 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="CONDENSEDCONSOLIDATEDSTATEMENTSOFCASHFLOWS" roleURI="http://www.spok.com/role/CONDENSEDCONSOLIDATEDSTATEMENTSOFCASHFLOWS">
        <link:definition>9952155 - Statement - CONDENSED CONSOLIDATED STATEMENTS OF CASH FLOWS</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="OrganizationandSignificantAccountingPolicies" roleURI="http://www.spok.com/role/OrganizationandSignificantAccountingPolicies">
        <link:definition>9952156 - Disclosure - Organization 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="RisksandOtherImportantFactors" roleURI="http://www.spok.com/role/RisksandOtherImportantFactors">
        <link:definition>9952157 - Disclosure - Risks and Other Important Factors</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="RecentAccountingStandards" roleURI="http://www.spok.com/role/RecentAccountingStandards">
        <link:definition>9952158 - Disclosure - Recent Accounting Standards</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="SignificantAccountingPolicies" roleURI="http://www.spok.com/role/SignificantAccountingPolicies">
        <link:definition>9952159 - Disclosure - 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="RevenueDeferredRevenueandPrepaidCommissions" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissions">
        <link:definition>9952160 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions</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.spok.com/role/Leases">
        <link:definition>9952161 - 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="CondensedConsolidatedFinancialStatementsComponents" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponents">
        <link:definition>9952162 - Disclosure - Condensed Consolidated Financial Statements' Components</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="Goodwill" roleURI="http://www.spok.com/role/Goodwill">
        <link:definition>9952163 - Disclosure - Goodwill</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="AssetRetirementObligations" roleURI="http://www.spok.com/role/AssetRetirementObligations">
        <link:definition>9952164 - Disclosure - Asset Retirement Obligations</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="StockholdersEquity" roleURI="http://www.spok.com/role/StockholdersEquity">
        <link:definition>9952165 - Disclosure - Stockholders' Equity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="IncomeTaxes" roleURI="http://www.spok.com/role/IncomeTaxes">
        <link:definition>9952166 - 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="CommitmentsandContingencies" roleURI="http://www.spok.com/role/CommitmentsandContingencies">
        <link:definition>9952167 - Disclosure - Commitments and Contingencies</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="RelatedParties" roleURI="http://www.spok.com/role/RelatedParties">
        <link:definition>9952168 - Disclosure - Related Parties</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SegmentInformation" roleURI="http://www.spok.com/role/SegmentInformation">
        <link:definition>9952169 - Disclosure - 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.spok.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="OrganizationandSignificantAccountingPoliciesPolicies" roleURI="http://www.spok.com/role/OrganizationandSignificantAccountingPoliciesPolicies">
        <link:definition>9955511 - Disclosure - Organization 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="RevenueDeferredRevenueandPrepaidCommissionsTables" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsTables">
        <link:definition>9955512 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions (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.spok.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="CondensedConsolidatedFinancialStatementsComponentsTables" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponentsTables">
        <link:definition>9955514 - Disclosure - Condensed Consolidated Financial Statements' Components (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="AssetRetirementObligationsTables" roleURI="http://www.spok.com/role/AssetRetirementObligationsTables">
        <link:definition>9955515 - Disclosure - Asset Retirement Obligations (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="StockholdersEquityTables" roleURI="http://www.spok.com/role/StockholdersEquityTables">
        <link:definition>9955516 - Disclosure - Stockholders' 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="RevenueDeferredRevenueandPrepaidCommissionsAdditionalInformationDetails" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsAdditionalInformationDetails">
        <link:definition>9955517 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions - Additional 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="RevenueDeferredRevenueandPrepaidCommissionsAdditionalInformationDetails_1" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsAdditionalInformationDetails_1">
        <link:definition>9955517 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions - Additional 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="RevenueDeferredRevenueandPrepaidCommissionsScheduleofRevenueDetails" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsScheduleofRevenueDetails">
        <link:definition>9955518 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions - Schedule 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="RevenueDeferredRevenueandPrepaidCommissionsDeferredRevenueDetails" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsDeferredRevenueDetails">
        <link:definition>9955519 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions - Deferred 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="RevenueDeferredRevenueandPrepaidCommissionsPrepaidCommissionsDetails" roleURI="http://www.spok.com/role/RevenueDeferredRevenueandPrepaidCommissionsPrepaidCommissionsDetails">
        <link:definition>9955520 - Disclosure - Revenue, Deferred Revenue and Prepaid Commissions - Prepaid Commissions (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="LeasesAdditionalInformationDetails" roleURI="http://www.spok.com/role/LeasesAdditionalInformationDetails">
        <link:definition>9955521 - Disclosure - Leases - Additional 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="LeasesLeaseCostsDetails" roleURI="http://www.spok.com/role/LeasesLeaseCostsDetails">
        <link:definition>9955522 - Disclosure - Leases - Lease Costs (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="LeasesLeaseMaturitiesDetails" roleURI="http://www.spok.com/role/LeasesLeaseMaturitiesDetails">
        <link:definition>9955523 - Disclosure - Leases - Lease Maturities (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="LeasesLeaseMaturitiesDetails_1" roleURI="http://www.spok.com/role/LeasesLeaseMaturitiesDetails_1">
        <link:definition>9955523 - Disclosure - Leases - Lease Maturities (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="CondensedConsolidatedFinancialStatementsComponentsDepreciationandAccretionDetails" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponentsDepreciationandAccretionDetails">
        <link:definition>9955524 - Disclosure - Condensed Consolidated Financial Statements' Components - Depreciation and Accretion (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="CondensedConsolidatedFinancialStatementsComponentsAccountsReceivableNetDetails" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponentsAccountsReceivableNetDetails">
        <link:definition>9955525 - Disclosure - Condensed Consolidated Financial Statements' Components - Accounts Receivable, Net (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="CondensedConsolidatedFinancialStatementsComponentsAllowanceforCreditLossesDetails" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponentsAllowanceforCreditLossesDetails">
        <link:definition>9955526 - Disclosure - Condensed Consolidated Financial Statements' Components - 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="CondensedConsolidatedFinancialStatementsComponentsPropertyandEquipmentNetDetails" roleURI="http://www.spok.com/role/CondensedConsolidatedFinancialStatementsComponentsPropertyandEquipmentNetDetails">
        <link:definition>9955527 - Disclosure - Condensed Consolidated Financial Statements' Components - Property and Equipment, Net (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="AssetRetirementObligationsChangesinAssetRetirementObligationLiabilitiesDetails" roleURI="http://www.spok.com/role/AssetRetirementObligationsChangesinAssetRetirementObligationLiabilitiesDetails">
        <link:definition>9955528 - Disclosure - Asset Retirement Obligations - Changes in Asset Retirement Obligation 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="AssetRetirementObligationsAdditionalInformationDetails" roleURI="http://www.spok.com/role/AssetRetirementObligationsAdditionalInformationDetails">
        <link:definition>9955529 - Disclosure - Asset Retirement Obligations - Additional 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="StockholdersEquityAdditionalInformationDetails" roleURI="http://www.spok.com/role/StockholdersEquityAdditionalInformationDetails">
        <link:definition>9955530 - Disclosure - Stockholders' Equity - Additional 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="StockholdersEquityCashDividendsDeclaredtoStockholdersDetails" roleURI="http://www.spok.com/role/StockholdersEquityCashDividendsDeclaredtoStockholdersDetails">
        <link:definition>9955531 - Disclosure - Stockholders' Equity - Cash Dividends Declared to Stockholders (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="StockholdersEquityBasicandDilutedNetIncomePerCommonShareDetails" roleURI="http://www.spok.com/role/StockholdersEquityBasicandDilutedNetIncomePerCommonShareDetails">
        <link:definition>9955532 - Disclosure - Stockholders' Equity - Basic and Diluted Net Income Per Common 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="StockholdersEquityActivitiesUnderEquityPlanDetails" roleURI="http://www.spok.com/role/StockholdersEquityActivitiesUnderEquityPlanDetails">
        <link:definition>9955533 - Disclosure - Stockholders' Equity - Activities Under Equity Plan (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="StockholdersEquityScheduleofOutstandingRSUsDetails" roleURI="http://www.spok.com/role/StockholdersEquityScheduleofOutstandingRSUsDetails">
        <link:definition>9955534 - Disclosure - Stockholders' Equity - Schedule of Outstanding RSUs (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="StockholdersEquityStockbasedCompensationExpenseDetails" roleURI="http://www.spok.com/role/StockholdersEquityStockbasedCompensationExpenseDetails">
        <link:definition>9955535 - Disclosure - Stockholders' Equity - Stock-based Compensation 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="IncomeTaxesDetails" roleURI="http://www.spok.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="RelatedPartiesDetails" roleURI="http://www.spok.com/role/RelatedPartiesDetails">
        <link:definition>9955537 - Disclosure - Related Parties (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType id="SubsequentEventDetails" roleURI="http://www.spok.com/role/SubsequentEventDetails">
        <link:definition>9955538 - 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="spok_WirelessOperationsMember" abstract="true" name="WirelessOperationsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_SoftwareOperationsMember" abstract="true" name="SoftwareOperationsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_TechnologyOperationsExpense" abstract="false" name="TechnologyOperationsExpense" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AdditionalPaidInCapitalAndAccumulatedOtherComprehensiveIncomeLossMember" abstract="true" name="AdditionalPaidInCapitalAndAccumulatedOtherComprehensiveIncomeLossMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_ProvisionsForDoubtfulAccountsServiceCreditsNoncashTaxesAndOther" abstract="false" name="ProvisionsForDoubtfulAccountsServiceCreditsNoncashTaxesAndOther" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_DepreciationAmortizationAndAccretionTableTableTextBlock" abstract="false" name="DepreciationAmortizationAndAccretionTableTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="spok_ActivitiesUnderEquityPlanFromInceptionTableTextBlock" abstract="false" name="ActivitiesUnderEquityPlanFromInceptionTableTextBlock" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:textBlockItemType"/>
  <xs:element id="spok_PrimaryRevenueSources" abstract="false" name="PrimaryRevenueSources" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="spok_RevenueFromContractWithCustomerContractTerm" abstract="false" name="RevenueFromContractWithCustomerContractTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="spok_RevenueExcludedFromRemainingPerformanceObligationAmount" abstract="false" name="RevenueExcludedFromRemainingPerformanceObligationAmount" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_PagingMember" abstract="true" name="PagingMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_ProfessionalServicesProjectsMember" abstract="true" name="ProfessionalServicesProjectsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_ProfessionalServicesManagedServicesMember" abstract="true" name="ProfessionalServicesManagedServicesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_HardwareMember" abstract="true" name="HardwareMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_ContractWithCustomerLiabilityRollForward" abstract="true" name="ContractWithCustomerLiabilityRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="spok_ContractWithCustomerLiabilityIncreaseFromAdditions" abstract="false" name="ContractWithCustomerLiabilityIncreaseFromAdditions" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_ContractWithCustomerLiabilityRevenueRecognizedIncludingOpeningBalance" abstract="false" name="ContractWithCustomerLiabilityRevenueRecognizedIncludingOpeningBalance" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_SalesCommissionsMember" abstract="true" name="SalesCommissionsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_CapitalizedContractCostRollForward" abstract="true" name="CapitalizedContractCostRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="spok_IncreaseDecreaseToCapitalizedContractCost" abstract="false" name="IncreaseDecreaseToCapitalizedContractCost" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_CapitalizedContractCostAmountRecognized" abstract="false" name="CapitalizedContractCostAmountRecognized" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_LesseeOperatingLeaseNumberOfRenewalTerms" abstract="false" name="LesseeOperatingLeaseNumberOfRenewalTerms" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="xbrli:integerItemType"/>
  <xs:element id="spok_LesseeOperatingLeaseTerminationTerm" abstract="false" name="LesseeOperatingLeaseTerminationTerm" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="spok_RightOfUseAssetObtainedInExchangeForOperatingLeaseLiabilityNetOfLeaseTermination" abstract="false" name="RightOfUseAssetObtainedInExchangeForOperatingLeaseLiabilityNetOfLeaseTermination" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_LesseeOperatingLeaseLiabilityToBePaidAfterYearFour" abstract="false" name="LesseeOperatingLeaseLiabilityToBePaidAfterYearFour" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AssetRetirementCostsMember" abstract="true" name="AssetRetirementCostsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_PagingandComputerEquipmentMember" abstract="true" name="PagingandComputerEquipmentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_FurnitureFixturesandVehiclesMember" abstract="true" name="FurnitureFixturesandVehiclesMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_DepreciationAppreciationAssetRetirementCosts" abstract="false" name="DepreciationAppreciationAssetRetirementCosts" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_DepreciationNetOfAssetRetirementCosts" abstract="false" name="DepreciationNetOfAssetRetirementCosts" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AccountsAndContractWithCustomerReceivableAllowanceForCreditLossCurrent" abstract="false" name="AccountsAndContractWithCustomerReceivableAllowanceForCreditLossCurrent" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AccountsAndContractWithCustomerReceivableCreditLossExpenseReversal" abstract="false" name="AccountsAndContractWithCustomerReceivableCreditLossExpenseReversal" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AccountsAndContractWithCustomerReceivableAllowanceForCreditLossWriteoff" abstract="false" name="AccountsAndContractWithCustomerReceivableAllowanceForCreditLossWriteoff" nillable="true" xbrli:periodType="duration" xbrli:balance="debit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_ScheduleOfAssetRetirementObligationLiabilitiesTable" abstract="true" name="ScheduleOfAssetRetirementObligationLiabilitiesTable" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrldt:hypercubeItem" type="xbrli:stringItemType"/>
  <xs:element id="spok_AssetRetirementObligationsNoncurrentMember" abstract="true" name="AssetRetirementObligationsNoncurrentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_AssetRetirementObligationLiabilitiesLineItems" abstract="true" name="AssetRetirementObligationLiabilitiesLineItems" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="spok_AssetRetirementObligationAccretionExpenseCredit" abstract="false" name="AssetRetirementObligationAccretionExpenseCredit" nillable="true" xbrli:periodType="duration" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_AssetRetirementObligationEstimatedLiabilityRemovalCostsAndTimingRefinements" abstract="false" name="AssetRetirementObligationEstimatedLiabilityRemovalCostsAndTimingRefinements" nillable="true" xbrli:periodType="instant" xbrli:balance="credit" substitutionGroup="xbrli:item" type="xbrli:monetaryItemType"/>
  <xs:element id="spok_A2020EquityPlanMember" abstract="true" name="A2020EquityPlanMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_A2020EquityPlanMemberMember" abstract="true" name="A2020EquityPlanMemberMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_EmployeeStockPurchasePlanMember" abstract="true" name="EmployeeStockPurchasePlanMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_ContingentRestrictedStockUnitsMember" abstract="true" name="ContingentRestrictedStockUnitsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_NonContingentRestrictedStockUnitsMember" abstract="true" name="NonContingentRestrictedStockUnitsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_RestrictedStockRestrictedStockUnitsAndDeferredStockUnitsMember" abstract="true" name="RestrictedStockRestrictedStockUnitsAndDeferredStockUnitsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_RestrictedStockUnitsWithContingentPerformanceRequirementsMember" abstract="true" name="RestrictedStockUnitsWithContingentPerformanceRequirementsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_RestrictedStockandRestrictedStockUnitsRSUsMember" abstract="true" name="RestrictedStockandRestrictedStockUnitsRSUsMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_CommonStockSharesIssuedNotDisclosed" abstract="false" name="CommonStockSharesIssuedNotDisclosed" nillable="true" xbrli:periodType="instant" substitutionGroup="xbrli:item" type="xbrli:booleanItemType"/>
  <xs:element id="spok_ShareBasedCompensationArrangementByShareBasedPaymentAwardAwardRequiredHoldingPeriod" abstract="false" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardAwardRequiredHoldingPeriod" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="spok_ShareBasedCompensationArrangementByShareBasedPaymentAwardOfferingPeriod" abstract="false" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOfferingPeriod" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:durationItemType"/>
  <xs:element id="spok_SharebasedCompensationArrangementBySharebasedPaymentAwardSharesAuthorizedRollForward" abstract="true" name="SharebasedCompensationArrangementBySharebasedPaymentAwardSharesAuthorizedRollForward" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:stringItemType"/>
  <xs:element id="spok_ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsGrantsInPeriodNetOfForfeitures" abstract="false" name="ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsGrantsInPeriodNetOfForfeitures" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="xbrli:sharesItemType"/>
  <xs:element id="spok_TimeBasedAwardsAndRestrictedStockMember" abstract="true" name="TimeBasedAwardsAndRestrictedStockMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
  <xs:element id="spok_StrategicRealignmentMember" abstract="true" name="StrategicRealignmentMember" nillable="true" xbrli:periodType="duration" substitutionGroup="xbrli:item" type="dtr-types:domainItemType"/>
</xs:schema>
