<?xml version="1.0" encoding="utf-8"?>
<!--XBRL document created with Toppan Merrill Bridge  11.3.0.1 -->
<!--Based on XBRL 2.1-->
<!--Created on: 5/20/2026 8:31:25 PM-->
<!--Modified on: 5/20/2026 8:31:25 PM-->
<xsd:schema targetNamespace="http://nationalbankholdings.com/20260228" attributeFormDefault="unqualified" elementFormDefault="qualified" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:dei="http://xbrl.sec.gov/dei/2026" xmlns:deprecated="http://www.xbrl.org/2009/role/deprecated" xmlns:dtr="http://www.xbrl.org/2009/dtr" xmlns:ref="http://www.xbrl.org/2006/ref" xmlns:xbrldt="http://xbrl.org/2005/xbrldt" xmlns:xl="http://www.xbrl.org/2003/XLink" xmlns:utr="http://www.xbrl.org/2009/utr" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:enum2="http://xbrl.org/2020/extensible-enumerations-2.0" xmlns:net="http://www.xbrl.org/2009/role/net" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2020-01-21" xmlns:xbrldi="http://xbrl.org/2006/xbrldi" xmlns:negated="http://www.xbrl.org/2009/role/negated" xmlns:srt="http://fasb.org/srt/2026" xmlns:attributeFormDefault="unqualified" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:us-gaap-ebp="http://fasb.org/us-gaap-ebp/2026" xmlns:nbhc="http://nationalbankholdings.com/20260228">
  <xsd:annotation>
    <xsd:appinfo>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DocumentDocumentAndEntityInformation" id="DocumentDocumentAndEntityInformation">
        <link:definition>00090 - Document - Document and Entity Information</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/StatementStatementsOfFinancialCondition" id="StatementStatementsOfFinancialCondition">
        <link:definition>00100 - Statement - Statements of Financial Condition</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/StatementStatementsOfIncomeAndChangesInPlanEquity" id="StatementStatementsOfIncomeAndChangesInPlanEquity">
        <link:definition>00200 - Statement - Statements of Income and Changes in Plan Equity</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureDescriptionOfPlan" id="DisclosureDescriptionOfPlan">
        <link:definition>10101 - Disclosure - DESCRIPTION OF THE PLAN</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureSummaryOfSignificantAccountingPolicies" id="DisclosureSummaryOfSignificantAccountingPolicies">
        <link:definition>10201 - Disclosure - SUMMARY OF SIGNIFICANT ACCOUNTING POLICIES</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureFederalIncomeTaxStatus" id="DisclosureFederalIncomeTaxStatus">
        <link:definition>10301 - Disclosure - FEDERAL INCOME TAX STATUS</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureDescriptionOfPlanTables" id="DisclosureDescriptionOfPlanTables">
        <link:definition>30103 - Disclosure - DESCRIPTION OF THE PLAN (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureDescriptionOfPlanDetails" id="DisclosureDescriptionOfPlanDetails">
        <link:definition>40101 - Disclosure - DESCRIPTION OF THE 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 roleURI="http://nationalbankholdings.com/role/DisclosureDescriptionOfPlanStockPurchaseProvisionsDetails" id="DisclosureDescriptionOfPlanStockPurchaseProvisionsDetails">
        <link:definition>40102 - Disclosure - DESCRIPTION OF THE PLAN - Stock Purchase Provisions (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:linkbaseRef xlink:type="simple" xlink:href="nbhc-20260228_pre.xml" xlink:role="http://www.xbrl.org/2003/role/presentationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="nbhc-20260228_def.xml" xlink:role="http://www.xbrl.org/2003/role/definitionLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="nbhc-20260228_lab.xml" xlink:role="http://www.xbrl.org/2003/role/labelLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:roleType roleURI="http://nationalbankholdings.com/role/DisclosureStandardAndCustomAxisDomainDefaults" id="DisclosureStandardAndCustomAxisDomainDefaults">
        <link:definition>99900 - Disclosure - Standard And Custom Axis Domain Defaults</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
    </xsd:appinfo>
  </xsd:annotation>
  <xsd:import namespace="http://fasb.org/us-gaap-ebp/2026" schemaLocation="https://xbrl.fasb.org/us-gaap/2026/ebp/elts/us-gaap-ebp-2026.xsd" />
  <xsd:import namespace="http://fasb.org/srt/2026" schemaLocation="https://xbrl.fasb.org/srt/2026/elts/srt-2026.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/dei/2026" schemaLocation="https://xbrl.sec.gov/dei/2026/dei-2026.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2003/instance" schemaLocation="http://www.xbrl.org/2003/xbrl-instance-2003-12-31.xsd" />
  <xsd:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <import namespace="http://www.xbrl.org/dtr/type/2020-01-21" schemaLocation="https://www.xbrl.org/dtr/type/2020-01-21/types.xsd" xmlns="http://www.w3.org/2001/XMLSchema" />
  <xsd:import namespace="http://www.xbrl.org/dtr/type/2024-01-31" schemaLocation="https://www.xbrl.org/dtr/type/2024-01-31/types.xsd" />
  <xsd:element name="EBP001Member" id="nbhc_EBP001Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="EbpEquityAbstractAbstract" id="nbhc_EbpEquityAbstractAbstract" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="EBPStockPurchaseProvisionsSharesPurchasedAndPurchasePriceTableTextBlock" id="nbhc_EBPStockPurchaseProvisionsSharesPurchasedAndPurchasePriceTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanMaximumSharesAuthorizedToIssue" id="nbhc_EmployeeBenefitPlanMaximumSharesAuthorizedToIssue" type="xbrli:sharesItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanNumberOfSharesAvailableForIssuance" id="nbhc_EmployeeBenefitPlanNumberOfSharesAvailableForIssuance" type="xbrli:sharesItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanMinimumServicePeriodForPlanEligibility" id="nbhc_EmployeeBenefitPlanMinimumServicePeriodForPlanEligibility" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanMinimumServiceHoursPerWeekForPlanEligibility" id="nbhc_EmployeeBenefitPlanMinimumServiceHoursPerWeekForPlanEligibility" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanRefundsOfParticipantContributionsOnWithdrawal" id="nbhc_EmployeeBenefitPlanRefundsOfParticipantContributionsOnWithdrawal" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="OfferingPeriodMarchToAugustMember" id="nbhc_OfferingPeriodMarchToAugustMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="OfferingPeriodSeptemberToFebruaryMember" id="nbhc_OfferingPeriodSeptemberToFebruaryMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="EmployeeBenefitPlanStockPurchasePricePercentageOfFairValue" id="nbhc_EmployeeBenefitPlanStockPurchasePricePercentageOfFairValue" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EmployeeBenefitPlanInvestmentPurchasedPricePerShare" id="nbhc_EmployeeBenefitPlanInvestmentPurchasedPricePerShare" type="dtr-types:perShareItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
</xsd:schema>
