<?xml version="1.0" encoding="utf-8"?>
<!--XBRL document created with Toppan Merrill Bridge  11.4.0.1 -->
<!--Based on XBRL 2.1-->
<!--Created on: 8/5/2026 9:11:10 PM-->
<!--Modified on: 8/5/2026 9:11:10 PM-->
<xsd:schema targetNamespace="http://www.nationalbankholdings.com/20260630" attributeFormDefault="unqualified" elementFormDefault="qualified" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:nbhc="http://www.nationalbankholdings.com/20260630" xmlns:deprecated="http://www.xbrl.org/2009/role/deprecated" xmlns:us-roles="http://fasb.org/us-roles/2026" 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:us-gaap="http://fasb.org/us-gaap/2026" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:stpr="http://xbrl.sec.gov/stpr/2026" xmlns:enum2="http://xbrl.org/2020/extensible-enumerations-2.0" xmlns:net="http://www.xbrl.org/2009/role/net" xmlns:dei="http://xbrl.sec.gov/dei/2026" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:dtr-types="http://www.xbrl.org/dtr/type/2024-01-31" xmlns:negated="http://www.xbrl.org/2009/role/negated" xmlns:attributeFormDefault="unqualified" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:srt="http://fasb.org/srt/2026" xmlns:xbrli="http://www.xbrl.org/2003/instance" xmlns:dtr="http://www.xbrl.org/2009/dtr" xmlns:xbrldi="http://xbrl.org/2006/xbrldi" xmlns:ecd="http://xbrl.sec.gov/ecd/2026" xmlns:ecd-sub="http://xbrl.sec.gov/ecd-sub/2026">
  <xsd:annotation>
    <xsd:appinfo>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfFinancialCondition" id="StatementConsolidatedStatementsOfFinancialCondition">
        <link:definition>995200100 - Statement - Consolidated 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://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfOperations" id="StatementConsolidatedStatementsOfOperations">
        <link:definition>995200200 - Statement - 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 roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfComprehensiveIncome" id="StatementConsolidatedStatementsOfComprehensiveIncome">
        <link:definition>995200300 - Statement - 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 roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfCashFlows" id="StatementConsolidatedStatementsOfCashFlows">
        <link:definition>995200500 - Statement - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureAcquisitionActivitiesSummaryOfNetAssetsAcquiredAndConsiderationTransferredDetails" id="DisclosureAcquisitionActivitiesSummaryOfNetAssetsAcquiredAndConsiderationTransferredDetails">
        <link:definition>99940302 - Disclosure - Acquisition Activities - Summary of Net Assets Acquired and Consideration transferred (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://www.nationalbankholdings.com/role/DisclosureAcquisitionActivitiesAccountingForAcquiredLoansDetails" id="DisclosureAcquisitionActivitiesAccountingForAcquiredLoansDetails">
        <link:definition>99940303 - Disclosure - Acquisition Activities - Accounting for acquired loans (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://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfAvailableForSaleInvestmentSecuritiesDetails" id="DisclosureInvestmentSecuritiesSummaryOfAvailableForSaleInvestmentSecuritiesDetails">
        <link:definition>99940402 - Disclosure - Investment Securities - Summary of Available-for-Sale Investment Securities (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfUnrealizedLossesDetails" id="DisclosureInvestmentSecuritiesSummaryOfUnrealizedLossesDetails">
        <link:definition>99940403 - Disclosure - Investment Securities - Summary of Unrealized 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfHeldToMaturityInvestmentSecuritiesDetails" id="DisclosureInvestmentSecuritiesSummaryOfHeldToMaturityInvestmentSecuritiesDetails">
        <link:definition>99940405 - Disclosure - Investment Securities - Summary of Held-to-maturity Investment Securities (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfHeldToMaturitySecuritiesUnrealizedLossesDetails" id="DisclosureInvestmentSecuritiesSummaryOfHeldToMaturitySecuritiesUnrealizedLossesDetails">
        <link:definition>99940406 - Disclosure - Investment Securities - Summary of Held-to-Maturity Securities, Unrealized 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureOtherSecuritiesCarryingBalanceDetails" id="DisclosureOtherSecuritiesCarryingBalanceDetails">
        <link:definition>99940501 - Disclosure - Other Securities - Carrying Balance (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://www.nationalbankholdings.com/role/DisclosureLoansLoanDelinquencyDetails" id="DisclosureLoansLoanDelinquencyDetails">
        <link:definition>99940602 - Disclosure - Loans - Loan Delinquency (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://www.nationalbankholdings.com/role/DisclosureLoansCarryingValueOfLoanPortfolioBySegmentAndCreditQualityIndicatorDetails" id="DisclosureLoansCarryingValueOfLoanPortfolioBySegmentAndCreditQualityIndicatorDetails">
        <link:definition>99940603 - Disclosure - Loans - Carrying Value of Loan Portfolio by Segment and Credit Quality Indicator (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://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssetsCarryingAmountsDetails" id="DisclosureGoodwillAndIntangibleAssetsCarryingAmountsDetails">
        <link:definition>99940802 - Disclosure - Goodwill and Intangible Assets - Carrying Amounts (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://www.nationalbankholdings.com/role/DisclosureRevenueFromContractsWithClientsNonInterestIncomeDetails" id="DisclosureRevenueFromContractsWithClientsNonInterestIncomeDetails">
        <link:definition>99941101 - Disclosure - Revenue from Contracts with Clients - Non-interest income (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://www.nationalbankholdings.com/role/DisclosureEarningsPerShareScheduleOfComputationOfBasicAndDilutedIncomePerShareDetails" id="DisclosureEarningsPerShareScheduleOfComputationOfBasicAndDilutedIncomePerShareDetails">
        <link:definition>99941402 - Disclosure - Earnings Per Share - Schedule of Computation of Basic and Diluted Income 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 roleURI="http://www.nationalbankholdings.com/role/DocumentDocumentAndEntityInformation" id="DocumentDocumentAndEntityInformation">
        <link:definition>995200090 - 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://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfFinancialConditionParenthetical" id="StatementConsolidatedStatementsOfFinancialConditionParenthetical">
        <link:definition>995200105 - Statement - Consolidated Statements of Financial Condition (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 roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfComprehensiveIncomeParenthetical" id="StatementConsolidatedStatementsOfComprehensiveIncomeParenthetical">
        <link:definition>995200305 - Statement - Consolidated Statements of Comprehensive Income (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 roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfChangesInShareholdersEquity" id="StatementConsolidatedStatementsOfChangesInShareholdersEquity">
        <link:definition>995200400 - Statement - Consolidated Statements of Changes in 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 roleURI="http://www.nationalbankholdings.com/role/StatementConsolidatedStatementsOfChangesInShareholdersEquityParenthetical" id="StatementConsolidatedStatementsOfChangesInShareholdersEquityParenthetical">
        <link:definition>995200405 - Statement - Consolidated Statements of Changes in Shareholders' Equity (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 roleURI="http://www.nationalbankholdings.com/role/DisclosureBasisOfPresentation" id="DisclosureBasisOfPresentation">
        <link:definition>995210101 - Disclosure - Basis of Presentation</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://www.nationalbankholdings.com/role/DisclosureRecentAccountingPronouncements" id="DisclosureRecentAccountingPronouncements">
        <link:definition>995210201 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureAcquisitionActivities" id="DisclosureAcquisitionActivities">
        <link:definition>995210301 - Disclosure - Acquisition 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecurities" id="DisclosureInvestmentSecurities">
        <link:definition>995210401 - Disclosure - Investment Securities</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://www.nationalbankholdings.com/role/DisclosureOtherSecurities" id="DisclosureOtherSecurities">
        <link:definition>995210501 - Disclosure - Other Securities</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://www.nationalbankholdings.com/role/DisclosureLoans" id="DisclosureLoans">
        <link:definition>995210601 - Disclosure - Loans</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://www.nationalbankholdings.com/role/DisclosureAllowanceForCreditLosses" id="DisclosureAllowanceForCreditLosses">
        <link:definition>995210701 - Disclosure - Allowance for Credit Losses</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://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssets" id="DisclosureGoodwillAndIntangibleAssets">
        <link:definition>995210801 - Disclosure - Goodwill and Intangible Assets</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://www.nationalbankholdings.com/role/DisclosureBorrowings" id="DisclosureBorrowings">
        <link:definition>995210901 - Disclosure - Borrowings</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://www.nationalbankholdings.com/role/DisclosureRegulatoryCapital" id="DisclosureRegulatoryCapital">
        <link:definition>995211001 - Disclosure - Regulatory Capital</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://www.nationalbankholdings.com/role/DisclosureRevenueFromContractsWithClients" id="DisclosureRevenueFromContractsWithClients">
        <link:definition>995211101 - Disclosure - Revenue from Contracts with Clients</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://www.nationalbankholdings.com/role/DisclosureStockBasedCompensationAndBenefits" id="DisclosureStockBasedCompensationAndBenefits">
        <link:definition>995211201 - Disclosure - Stock-based Compensation and 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureCommonStock" id="DisclosureCommonStock">
        <link:definition>995211301 - Disclosure - Common Stock</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://www.nationalbankholdings.com/role/DisclosureEarningsPerShare" id="DisclosureEarningsPerShare">
        <link:definition>995211401 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureDerivatives" id="DisclosureDerivatives">
        <link:definition>995211501 - Disclosure - Derivatives</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://www.nationalbankholdings.com/role/DisclosureCommitmentsAndContingencies" id="DisclosureCommitmentsAndContingencies">
        <link:definition>995211601 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureFairValueMeasurements" id="DisclosureFairValueMeasurements">
        <link:definition>995211701 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureFairValueOfFinancialInstruments" id="DisclosureFairValueOfFinancialInstruments">
        <link:definition>995211801 - Disclosure - Fair Value of Financial Instruments</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureAcquisitionActivitiesTables" id="DisclosureAcquisitionActivitiesTables">
        <link:definition>99930303 - Disclosure - Acquisition 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesTables" id="DisclosureInvestmentSecuritiesTables">
        <link:definition>99930403 - Disclosure - Investment Securities (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://www.nationalbankholdings.com/role/DisclosureLoansTables" id="DisclosureLoansTables">
        <link:definition>99930603 - Disclosure - Loans (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://www.nationalbankholdings.com/role/DisclosureAllowanceForCreditLossesTables" id="DisclosureAllowanceForCreditLossesTables">
        <link:definition>99930703 - Disclosure - Allowance for Credit Losses (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://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssetsTables" id="DisclosureGoodwillAndIntangibleAssetsTables">
        <link:definition>99930803 - Disclosure - Goodwill and Intangible Assets (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://www.nationalbankholdings.com/role/DisclosureRegulatoryCapitalTables" id="DisclosureRegulatoryCapitalTables">
        <link:definition>99931003 - Disclosure - Regulatory Capital (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://www.nationalbankholdings.com/role/DisclosureRevenueFromContractsWithClientsTables" id="DisclosureRevenueFromContractsWithClientsTables">
        <link:definition>99931103 - Disclosure - Revenue from Contracts with Clients (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://www.nationalbankholdings.com/role/DisclosureStockBasedCompensationAndBenefitsTables" id="DisclosureStockBasedCompensationAndBenefitsTables">
        <link:definition>99931203 - Disclosure - Stock-based Compensation and 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureEarningsPerShareTables" id="DisclosureEarningsPerShareTables">
        <link:definition>99931403 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureDerivativesTables" id="DisclosureDerivativesTables">
        <link:definition>99931503 - Disclosure - Derivatives (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://www.nationalbankholdings.com/role/DisclosureCommitmentsAndContingenciesTables" id="DisclosureCommitmentsAndContingenciesTables">
        <link:definition>99931603 - Disclosure - Commitments and Contingencies (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://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsTables" id="DisclosureFairValueMeasurementsTables">
        <link:definition>99931703 - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureFairValueOfFinancialInstrumentsTables" id="DisclosureFairValueOfFinancialInstrumentsTables">
        <link:definition>99931803 - Disclosure - Fair Value of Financial Instruments (Tables)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureBasisOfPresentationDetails" id="DisclosureBasisOfPresentationDetails">
        <link:definition>99940101 - Disclosure - Basis of Presentation (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://www.nationalbankholdings.com/role/DisclosureAcquisitionActivitiesNarrativeDetails" id="DisclosureAcquisitionActivitiesNarrativeDetails">
        <link:definition>99940301 - Disclosure - Acquisition 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureAcquisitionActivitiesUnauditedProFormaInformationDetails" id="DisclosureAcquisitionActivitiesUnauditedProFormaInformationDetails">
        <link:definition>99940304 - Disclosure - Acquisition Activities - Unaudited Pro forma 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesNarrativeDetails" id="DisclosureInvestmentSecuritiesNarrativeDetails">
        <link:definition>99940401 - Disclosure - Investment Securities - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfAvailableForSaleSecuritiesByMaturityDetails" id="DisclosureInvestmentSecuritiesSummaryOfAvailableForSaleSecuritiesByMaturityDetails">
        <link:definition>99940404 - Disclosure - Investment Securities - Summary of Available-for-sale Securities By Maturity (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://www.nationalbankholdings.com/role/DisclosureInvestmentSecuritiesSummaryOfCreditQualityIndicatorsOfHeldToMaturityInvestmentSecuritiesDetails" id="DisclosureInvestmentSecuritiesSummaryOfCreditQualityIndicatorsOfHeldToMaturityInvestmentSecuritiesDetails">
        <link:definition>99940407 - Disclosure - Investment Securities - Summary of Credit Quality Indicators of Held-to-maturity Investment Securities (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureOtherSecuritiesNarrativeDetails" id="DisclosureOtherSecuritiesNarrativeDetails">
        <link:definition>99940502 - Disclosure - Other Securities - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureLoansLoanPortfolioCompositionIncludingCarryingValueBySegmentOfLoansAccountedForUnderAscTopic31030Details" id="DisclosureLoansLoanPortfolioCompositionIncludingCarryingValueBySegmentOfLoansAccountedForUnderAscTopic31030Details">
        <link:definition>99940601 - Disclosure - Loans - Loan Portfolio Composition Including Carrying Value by Segment of Loans Accounted for under ASC Topic 310-30 (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://www.nationalbankholdings.com/role/DisclosureLoansCollateralDependentLoansDetails" id="DisclosureLoansCollateralDependentLoansDetails">
        <link:definition>99940604 - Disclosure - Loans - Collateral Dependent Loans (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://www.nationalbankholdings.com/role/DisclosureLoansScheduleOfModifiedLoansToBorrowersExperiencingFinancialDifficultyDetails" id="DisclosureLoansScheduleOfModifiedLoansToBorrowersExperiencingFinancialDifficultyDetails">
        <link:definition>99940605 - Disclosure - Loans - Schedule of Modified Loans to Borrowers Experiencing Financial Difficulty (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://www.nationalbankholdings.com/role/DisclosureLoansScheduleOfPaymentStatusOfFinancingReceivableModifiedPast12MonthsDetails" id="DisclosureLoansScheduleOfPaymentStatusOfFinancingReceivableModifiedPast12MonthsDetails">
        <link:definition>99940606 - Disclosure - Loans - Schedule of Payment Status of Financing Receivable Modified Past 12 Months (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://www.nationalbankholdings.com/role/DisclosureLoansScheduleOfFinancialEffectOfLoanRestructuringModificationsDetails" id="DisclosureLoansScheduleOfFinancialEffectOfLoanRestructuringModificationsDetails">
        <link:definition>99940607 - Disclosure - Loans - Schedule of Financial Effect of Loan Restructuring Modifications (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://www.nationalbankholdings.com/role/DisclosureAllowanceForCreditLossesSummaryOfCompanySAllowanceForLoanLossesallAndRecordedInvestmentInLoansDetails" id="DisclosureAllowanceForCreditLossesSummaryOfCompanySAllowanceForLoanLossesallAndRecordedInvestmentInLoansDetails">
        <link:definition>99940701 - Disclosure - Allowance for Credit Losses - Summary of Company's Allowance for Loan Losses ("All") and Recorded Investment in Loans (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://www.nationalbankholdings.com/role/DisclosureAllowanceForCreditLossesNarrativeDetails" id="DisclosureAllowanceForCreditLossesNarrativeDetails">
        <link:definition>99940702 - Disclosure - Allowance for Credit Losses - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssetsNarrativeDetails" id="DisclosureGoodwillAndIntangibleAssetsNarrativeDetails">
        <link:definition>99940801 - Disclosure - Goodwill and Intangible Assets - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssetsSummaryOfEstimatedFutureAmortizationExpenseDetails" id="DisclosureGoodwillAndIntangibleAssetsSummaryOfEstimatedFutureAmortizationExpenseDetails">
        <link:definition>99940803 - Disclosure - Goodwill and Intangible Assets - Summary of Estimated Future Amortization 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureGoodwillAndIntangibleAssetsChangesInServicingRightsDetails" id="DisclosureGoodwillAndIntangibleAssetsChangesInServicingRightsDetails">
        <link:definition>99940804 - Disclosure - Goodwill and Intangible Assets - Changes in Servicing Rights (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://www.nationalbankholdings.com/role/DisclosureBorrowingsNarrativeDetails" id="DisclosureBorrowingsNarrativeDetails">
        <link:definition>99940901 - Disclosure - Borrowings - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureRegulatoryCapitalCapitalRatioRequirementsUnderPromptCorrectiveActionOrOtherRegulatoryRequirementsDetails" id="DisclosureRegulatoryCapitalCapitalRatioRequirementsUnderPromptCorrectiveActionOrOtherRegulatoryRequirementsDetails">
        <link:definition>99941001 - Disclosure - Regulatory Capital - Capital Ratio Requirements under Prompt Corrective Action or Other Regulatory Requirements (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://www.nationalbankholdings.com/role/DisclosureStockBasedCompensationAndBenefitsNarrativeDetails" id="DisclosureStockBasedCompensationAndBenefitsNarrativeDetails">
        <link:definition>99941201 - Disclosure - Stock-based Compensation and Benefits - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureStockBasedCompensationAndBenefitsSummaryOfRestrictedStockAndPsuActivityDetails" id="DisclosureStockBasedCompensationAndBenefitsSummaryOfRestrictedStockAndPsuActivityDetails">
        <link:definition>99941202 - Disclosure - Stock-based Compensation and Benefits - Summary of Restricted Stock and PSU Activity (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://www.nationalbankholdings.com/role/DisclosureCommonStockNarrativeDetails" id="DisclosureCommonStockNarrativeDetails">
        <link:definition>99941301 - Disclosure - Common Stock - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureEarningsPerShareNarrativeDetails" id="DisclosureEarningsPerShareNarrativeDetails">
        <link:definition>99941401 - Disclosure - Earnings 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureDerivativesFvOfDerivativesOnBalanceSheetDetails" id="DisclosureDerivativesFvOfDerivativesOnBalanceSheetDetails">
        <link:definition>99941501 - Disclosure - Derivatives - FV of Derivatives on the Balance Sheet (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://www.nationalbankholdings.com/role/DisclosureDerivativesFvOfDerivativesOnBalanceSheetDefaultDetails" id="DisclosureDerivativesFvOfDerivativesOnBalanceSheetDefaultDetails">
        <link:definition>41501 - Disclosure - Derivatives - FV of Derivatives on the Balance Sheet Default (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://www.nationalbankholdings.com/role/DisclosureDerivativesNarrativeDetails" id="DisclosureDerivativesNarrativeDetails">
        <link:definition>99941502 - Disclosure - Derivatives - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureDerivativesScheduleOfCarryingAmountOfHedgedAssetsAndHedgingAdjustmentDetails" id="DisclosureDerivativesScheduleOfCarryingAmountOfHedgedAssetsAndHedgingAdjustmentDetails">
        <link:definition>99941503 - Disclosure - Derivatives - Schedule of carrying amount of hedged assets and hedging adjustment (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://www.nationalbankholdings.com/role/DisclosureDerivativesDerivativesOnIncomeStatementDetails" id="DisclosureDerivativesDerivativesOnIncomeStatementDetails">
        <link:definition>99941504 - Disclosure - Derivatives - Derivatives on the Income Statement (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://www.nationalbankholdings.com/role/DisclosureDerivativesDerivativesOnIncomeStatementDefaultDetails" id="DisclosureDerivativesDerivativesOnIncomeStatementDefaultDetails">
        <link:definition>41504 - Disclosure - Derivatives - Derivatives on the Income Statement Default (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://www.nationalbankholdings.com/role/DisclosureDerivativesEffectOfFairValueCashFlowHedgeAccountingOnAociDetails" id="DisclosureDerivativesEffectOfFairValueCashFlowHedgeAccountingOnAociDetails">
        <link:definition>99941505 - Disclosure - Derivatives - Effect of fair value cash flow hedge accounting on AOCI (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://www.nationalbankholdings.com/role/DisclosureDerivativesEffectOfFairValueCashFlowHedgeAccountingOnAociDefaultDetails" id="DisclosureDerivativesEffectOfFairValueCashFlowHedgeAccountingOnAociDefaultDetails">
        <link:definition>41505 - Disclosure - Derivatives - Effect of fair value cash flow hedge accounting on AOCI Default (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://www.nationalbankholdings.com/role/DisclosureCommitmentsAndContingenciesScheduleOfTotalUnfundedCommitmentsDetails" id="DisclosureCommitmentsAndContingenciesScheduleOfTotalUnfundedCommitmentsDetails">
        <link:definition>99941601 - Disclosure - Commitments and Contingencies - Schedule of Total Unfunded Commitments (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://www.nationalbankholdings.com/role/DisclosureCommitmentsAndContingenciesRepurchaseReserveActivityDetails" id="DisclosureCommitmentsAndContingenciesRepurchaseReserveActivityDetails">
        <link:definition>99941602 - Disclosure - Commitments and Contingencies - Repurchase Reserve Activity (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://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsAdditionalInformationDetails" id="DisclosureFairValueMeasurementsAdditionalInformationDetails">
        <link:definition>99941702 - Disclosure - Fair Value Measurements - 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 roleURI="http://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsTablesOfFinancialInstrumentsMeasuredAtFairValueOnRecurringBasisDetails" id="DisclosureFairValueMeasurementsTablesOfFinancialInstrumentsMeasuredAtFairValueOnRecurringBasisDetails">
        <link:definition>99941703 - Disclosure - Fair Value Measurements - Tables of Financial Instruments Measured At Fair Value on Recurring Basis (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://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsTableOfChangesInLevel3FinancialInstrumentsDetails" id="DisclosureFairValueMeasurementsTableOfChangesInLevel3FinancialInstrumentsDetails">
        <link:definition>99941704 - Disclosure - Fair Value Measurements - Table of Changes in Level 3 Financial Instruments (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsInputsUsedToDetermineFairValuesOfOreoAreConsideredLevel3InputsInFairValueHierarchyDetails" id="DisclosureFairValueMeasurementsInputsUsedToDetermineFairValuesOfOreoAreConsideredLevel3InputsInFairValueHierarchyDetails">
        <link:definition>99941705 - Disclosure - Fair Value Measurements - Inputs Used to Determine Fair Values of Oreo are Considered Level 3 Inputs in Fair Value Hierarchy (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://www.nationalbankholdings.com/role/DisclosureFairValueOfFinancialInstrumentsScheduleOfFairValueOfFinancialInstrumentsDetails" id="DisclosureFairValueOfFinancialInstrumentsScheduleOfFairValueOfFinancialInstrumentsDetails">
        <link:definition>99941801 - Disclosure - Fair Value of Financial Instruments - Schedule of Fair Value of Financial Instruments (Details)</link:definition>
        <link:usedOn>link:presentationLink</link:usedOn>
        <link:usedOn>link:calculationLink</link:usedOn>
        <link:usedOn>link:definitionLink</link:usedOn>
      </link:roleType>
      <link:roleType roleURI="http://www.nationalbankholdings.com/role/DisclosureBusinessSegment" id="DisclosureBusinessSegment">
        <link:definition>995211901 - Disclosure - Business Segment</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://www.nationalbankholdings.com/role/DisclosureOtherSecuritiesTables" id="DisclosureOtherSecuritiesTables">
        <link:definition>99930503 - Disclosure - Other Securities (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://www.nationalbankholdings.com/role/DisclosureFairValueMeasurementsTransferBetweenHierarchyLevelsDetails" id="DisclosureFairValueMeasurementsTransferBetweenHierarchyLevelsDetails">
        <link:definition>99941701 - Disclosure - Fair Value Measurements - Transfer Between Hierarchy Levels (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://www.nationalbankholdings.com/role/DisclosureBusinessSegmentDetails" id="DisclosureBusinessSegmentDetails">
        <link:definition>99941901 - Disclosure - Business Segment (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-20260630_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-20260630_cal.xml" xlink:role="http://www.xbrl.org/2003/role/calculationLinkbaseRef" xlink:arcrole="http://www.w3.org/1999/xlink/properties/linkbase" />
      <link:linkbaseRef xlink:type="simple" xlink:href="nbhc-20260630_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-20260630_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://www.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="https://xbrl.org/2023/calculation-1.1" schemaLocation="https://www.xbrl.org/2023/calculation-1.1.xsd" />
  <xsd:import namespace="http://xbrl.sec.gov/ecd/2026" schemaLocation="https://xbrl.sec.gov/ecd/2026/ecd-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://xbrl.sec.gov/stpr/2026" schemaLocation="https://xbrl.sec.gov/stpr/2026/stpr-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://www.xbrl.org/2009/role/negated" schemaLocation="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd" />
  <xsd:import namespace="http://www.xbrl.org/2009/role/net" schemaLocation="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd" />
  <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:import namespace="http://xbrl.org/2005/xbrldt" schemaLocation="http://www.xbrl.org/2005/xbrldt-2005.xsd" />
  <xsd:import namespace="http://fasb.org/us-roles/2026" schemaLocation="https://xbrl.fasb.org/us-gaap/2026/elts/us-roles-2026.xsd" />
  <xsd:import namespace="http://fasb.org/us-gaap/2026" schemaLocation="https://xbrl.fasb.org/us-gaap/2026/elts/us-gaap-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/ecd-sub/2026" schemaLocation="https://xbrl.sec.gov/ecd/2026/ecd-sub-2026.xsd" />
  <xsd:element name="PremisesAndEquipmentMember" id="nbhc_PremisesAndEquipmentMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="AcquisitionAndDevelopmentLoansMember" id="nbhc_AcquisitionAndDevelopmentLoansMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="AllowanceForLoanAndLeaseLossesLineItems" id="nbhc_AllowanceForLoanAndLeaseLossesLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="AllowanceForLoanLossesAndCreditQualityTable" id="nbhc_AllowanceForLoanLossesAndCreditQualityTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="AtmInterchangeAndCreditCardExpenses" id="nbhc_AtmInterchangeAndCreditCardExpenses" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="CollateralDependentImpairedLoansMember" id="nbhc_CollateralDependentImpairedLoansMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="CommitmentAndContingenciesLineItems" id="nbhc_CommitmentAndContingenciesLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="CommitmentsAndContingenciesTableTextBlock" id="nbhc_CommitmentsAndContingenciesTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FairValueOfImpairedLoansMember" id="nbhc_FairValueOfImpairedLoansMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="HeldtomaturitysecuritiescontinuousunrealizedlosspositionfairvalueTableTextBlock" id="nbhc_HeldtomaturitysecuritiescontinuousunrealizedlosspositionfairvalueTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="LoansAndLeasesReceivableTableTextBlock" id="nbhc_LoansAndLeasesReceivableTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="LoansHeldForSaleMaximumPeriodOfSale" id="nbhc_LoansHeldForSaleMaximumPeriodOfSale" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="LoansLineItems" id="nbhc_LoansLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="LoansPurchasedButNotSettled" id="nbhc_LoansPurchasedButNotSettled" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="MultiFamilyAndCommercialMember" id="nbhc_MultiFamilyAndCommercialMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="NonOwnerOccupiedCommercialMember" id="nbhc_NonOwnerOccupiedCommercialMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="NumberOfFullServiceBankingOffices" id="nbhc_NumberOfFullServiceBankingOffices" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="NumberOfLoansMeasured" id="nbhc_NumberOfLoansMeasured" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="OtherAvailableForSaleSecuritiesInvestmentsMember" id="nbhc_OtherAvailableForSaleSecuritiesInvestmentsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="OtherComprehensiveIncomeAmortizationOfNetUnrealizedHoldingGainsToIncomeDuringPeriodNetOfTax" id="nbhc_OtherComprehensiveIncomeAmortizationOfNetUnrealizedHoldingGainsToIncomeDuringPeriodNetOfTax" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="OtherComprehensiveIncomeAmortizationOfNetUnrealizedHoldingGainsToIncomeDuringPeriodTax" id="nbhc_OtherComprehensiveIncomeAmortizationOfNetUnrealizedHoldingGainsToIncomeDuringPeriodTax" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="OwnerOccupiedCommercialMember" id="nbhc_OwnerOccupiedCommercialMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ResidentialMortgageBackedAgencyMember" id="nbhc_ResidentialMortgageBackedAgencyMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ScheduleOfCommonStockLineItems" id="nbhc_ScheduleOfCommonStockLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ScheduleOfCommonStockTable" id="nbhc_ScheduleOfCommonStockTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="SubsidiaryMember" id="nbhc_SubsidiaryMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FairValueInputsWeightedAverageExpectedTerm" id="nbhc_FairValueInputsWeightedAverageExpectedTerm" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="AmountOfRepurchaseAgreement" id="nbhc_AmountOfRepurchaseAgreement" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="BusinessCombinationRecognizedIdentifiableAssetsAcquiredAndLiabilitiesAssumedCurrentAssetsNonMarketableSecurities" id="nbhc_BusinessCombinationRecognizedIdentifiableAssetsAcquiredAndLiabilitiesAssumedCurrentAssetsNonMarketableSecurities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="BusinessCombinationRecognizedIdentifiableAssetsAcquiredAndLiabilitiesAssumedOtherRealEstateOwned" id="nbhc_BusinessCombinationRecognizedIdentifiableAssetsAcquiredAndLiabilitiesAssumedOtherRealEstateOwned" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="CommitmentAndContingenciesTable" id="nbhc_CommitmentAndContingenciesTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="UnfundedCommitmentLineOfCreditMember" id="nbhc_UnfundedCommitmentLineOfCreditMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="CommercialAndStandbyLettersOfCreditMember" id="nbhc_CommercialAndStandbyLettersOfCreditMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="UnfundedLoanCommitments" id="nbhc_UnfundedLoanCommitments" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="instant" />
  <xsd:element name="GainOrLossOnReissuanceOfTreasuryStock" id="nbhc_GainOrLossOnReissuanceOfTreasuryStock" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardMaximumEmployeeStockPurchasePerCalendarYearValue" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardMaximumEmployeeStockPurchasePerCalendarYearValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="CommercialAndIndustrialLoanMember" id="nbhc_CommercialAndIndustrialLoanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardAwardPerformancePeriod" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardAwardPerformancePeriod" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsPercentageOfAwardBasedOnPerformanceCondition" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsPercentageOfAwardBasedOnPerformanceCondition" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="DerivativeFinancialInstrumentsAssetsAndLiabilitiesMember" id="nbhc_DerivativeFinancialInstrumentsAssetsAndLiabilitiesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ForwardContractNotionalMember" id="nbhc_ForwardContractNotionalMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="LoansHeldForSaleMember" id="nbhc_LoansHeldForSaleMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="MortgageServicingRightsMember" id="nbhc_MortgageServicingRightsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="MortgageLoansServiced" id="nbhc_MortgageLoansServiced" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="FiniteLivedIntangibleAssetsOriginations" id="nbhc_FiniteLivedIntangibleAssetsOriginations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="CommonEquityTier1CapitalConservationBufferRatio" id="nbhc_CommonEquityTier1CapitalConservationBufferRatio" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="CumulativeFairValueHedgeAdjustment" id="nbhc_CumulativeFairValueHedgeAdjustment" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="OtherNonInterestIncomeMember" id="nbhc_OtherNonInterestIncomeMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="InterestRateLockCommitmentsNotionalAmountMember" id="nbhc_InterestRateLockCommitmentsNotionalAmountMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="MortgageServiceFees" id="nbhc_MortgageServiceFees" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="CommonEquityTierOneRiskBasedCapitalRequiredToBeWellCapitalizedToRiskWeightedAssets" id="nbhc_CommonEquityTierOneRiskBasedCapitalRequiredToBeWellCapitalizedToRiskWeightedAssets" type="xbrli:pureItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardInitialTargetAwardPercentage" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardInitialTargetAwardPercentage" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FoodAndAgricultureLoanMember" id="nbhc_FoodAndAgricultureLoanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FinancingReceivables30To89DaysPastDueMember" id="nbhc_FinancingReceivables30To89DaysPastDueMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FinancingReceivableRecordedInvestmentPastDueAndNonaccrualStatus" id="nbhc_FinancingReceivableRecordedInvestmentPastDueAndNonaccrualStatus" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsAdjustmentsInPeriod" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsAdjustmentsInPeriod" type="xbrli:sharesItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsAdjustmentsInPeriodWeightedAverageGrantDateFairValue" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardEquityInstrumentsOtherThanOptionsAdjustmentsInPeriodWeightedAverageGrantDateFairValue" type="dtr-types:perShareItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="AvailableForSaleSecuritiesDebtMaturitiesTwelveMonthsOrGreaterFairValue" id="nbhc_AvailableForSaleSecuritiesDebtMaturitiesTwelveMonthsOrGreaterFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="CollateralDependentLoansReceivableAtAmortizedCostBasis" id="nbhc_CollateralDependentLoansReceivableAtAmortizedCostBasis" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="CollateralDependentLoansThresholdAmountOfLoansWithAmortizedCostBasisEvaluatedByManagement" id="nbhc_CollateralDependentLoansThresholdAmountOfLoansWithAmortizedCostBasisEvaluatedByManagement" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="ScheduleOfCollateralDependentLoansTableTextBlock" id="nbhc_ScheduleOfCollateralDependentLoansTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="InterestRateLockCommitmentsAveragePercentageOfEstimatedPullThroughRateToCalculateFairValue" id="nbhc_InterestRateLockCommitmentsAveragePercentageOfEstimatedPullThroughRateToCalculateFairValue" type="xbrli:pureItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="FederalDepositInsuranceCorporationPremiumExpenseBenefit" id="nbhc_FederalDepositInsuranceCorporationPremiumExpenseBenefit" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="LoansSoldSubjectToRepurchaseAllowanceForCreditLossTableTextBlock" id="nbhc_LoansSoldSubjectToRepurchaseAllowanceForCreditLossTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="PaymentsForOriginationAndPurchasesOfMortgageServicingRights" id="nbhc_PaymentsForOriginationAndPurchasesOfMortgageServicingRights" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="GainLossOnSaleOfMortgageServicingRights" id="nbhc_GainLossOnSaleOfMortgageServicingRights" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="MortgageServicingRightsMsrsUnpaidPrincipalBalances" id="nbhc_MortgageServicingRightsMsrsUnpaidPrincipalBalances" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="ProceedsFromSaleOfMortgageServicingRightsMsrOperatingActivities" id="nbhc_ProceedsFromSaleOfMortgageServicingRightsMsrOperatingActivities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="FixedToFloatingRateNoteMaturingNovember2031Member" id="nbhc_FixedToFloatingRateNoteMaturingNovember2031Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="OtherNonMarketableInvestments" id="nbhc_OtherNonMarketableInvestments" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardOfferingPeriod" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardOfferingPeriod" type="xbrli:durationItemType" substitutionGroup="xbrli:item" abstract="false" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="UsTreasurySecuritiesUsStatesAndPoliticalSubdivisionsDebtSecuritiesAndCorporateDebtSecuritiesMember" id="nbhc_UsTreasurySecuritiesUsStatesAndPoliticalSubdivisionsDebtSecuritiesAndCorporateDebtSecuritiesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="BankOfJacksonHoleMember" id="nbhc_BankOfJacksonHoleMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="SbaServicingRightsMember" id="nbhc_SbaServicingRightsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="OtherComprehensiveIncomeLossDerivativeIncludedComponentIncreaseDecreaseBeforeAdjustmentsAfterTax" id="nbhc_OtherComprehensiveIncomeLossDerivativeIncludedComponentIncreaseDecreaseBeforeAdjustmentsAfterTax" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" abstract="false" nillable="true" xbrli:balance="credit" xbrli:periodType="duration" />
  <xsd:element name="LossReclassifiedFromAociIntoIncomeIncludedComponent" id="nbhc_LossReclassifiedFromAociIntoIncomeIncludedComponent" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" abstract="false" nillable="true" xbrli:balance="debit" xbrli:periodType="duration" />
  <xsd:element name="MortgageLoansMember" id="nbhc_MortgageLoansMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="BankServicingChargesAndOtherFeesMember" id="nbhc_BankServicingChargesAndOtherFeesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" abstract="true" nillable="true" xbrli:periodType="duration" />
  <xsd:element name="DebtSecuritiesAvailableForSaleExcessCollateralPledged" id="nbhc_DebtSecuritiesAvailableForSaleExcessCollateralPledged" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" abstract="false" nillable="true" xbrli:balance="debit" xbrli:periodType="instant" />
  <xsd:element name="DebtSecuritiesHeldToMaturityUnrealizedLossPositionAccumulatedLossTotal1" id="nbhc_DebtSecuritiesHeldToMaturityUnrealizedLossPositionAccumulatedLossTotal1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DebtSecuritiesHeldToMaturityUnrealizedLossPositionFairValueTotal1" id="nbhc_DebtSecuritiesHeldToMaturityUnrealizedLossPositionFairValueTotal1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPosition12MonthsOrLongerAccumulatedLoss1" id="nbhc_DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPosition12MonthsOrLongerAccumulatedLoss1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPositionLessThan12MonthsFairValue1" id="nbhc_DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPositionLessThan12MonthsFairValue1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPosition12MonthsOrLongerFairValue1" id="nbhc_DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPosition12MonthsOrLongerFairValue1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="HeldToMaturitySecuritiesInUnrealizedLossPositionsQualitativeDisclosureNumberOfPositions1" id="nbhc_HeldToMaturitySecuritiesInUnrealizedLossPositionsQualitativeDisclosureNumberOfPositions1" type="xbrli:decimalItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="ImpairedFinancingReceivableWithRelatedAllowanceRecordedInvestment1" id="nbhc_ImpairedFinancingReceivableWithRelatedAllowanceRecordedInvestment1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPositionLessThan12MonthsAccumulatedLoss1" id="nbhc_DebtSecuritiesHeldToMaturityContinuousUnrealizedLossPositionLessThan12MonthsAccumulatedLoss1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="ScheduleOfChangesInSmallBusinessAdministrationServicingAssetsTableTextBlock" id="nbhc_ScheduleOfChangesInSmallBusinessAdministrationServicingAssetsTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="FiniteLivedIntangibleAssetsDisposals" id="nbhc_FiniteLivedIntangibleAssetsDisposals" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="NumberOfSubordinatedNotePurchaseAgreementsAssumed" id="nbhc_NumberOfSubordinatedNotePurchaseAgreementsAssumed" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="FixedToFloatingRateNoteMaturingJune2031Member" id="nbhc_FixedToFloatingRateNoteMaturingJune2031Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="TierOneRiskBasedCapitalRequiredForCapitalAdequacyWithCapitalConservationBufferToRiskWeightedAssets" id="nbhc_TierOneRiskBasedCapitalRequiredForCapitalAdequacyWithCapitalConservationBufferToRiskWeightedAssets" type="xbrli:pureItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="TierOneRiskBasedCapitalRequiredForCapitalAdequacyWithCapitalConservationBuffer" id="nbhc_TierOneRiskBasedCapitalRequiredForCapitalAdequacyWithCapitalConservationBuffer" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FairValueAssetsLevel1ToLevel2TransfersAmount1" id="nbhc_FairValueAssetsLevel1ToLevel2TransfersAmount1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FairValueAssetsLevel2ToLevel1TransfersAmount1" id="nbhc_FairValueAssetsLevel2ToLevel1TransfersAmount1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FairValueLiabilitiesLevel1ToLevel2TransfersAmount1" id="nbhc_FairValueLiabilitiesLevel1ToLevel2TransfersAmount1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="FairValueLiabilitiesLevel2ToLevel1TransfersAmount1" id="nbhc_FairValueLiabilitiesLevel2ToLevel1TransfersAmount1" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="ScheduleOfModifiedLoansToBorrowersExperiencingFinancialDifficultyTableTextBlock" id="nbhc_ScheduleOfModifiedLoansToBorrowersExperiencingFinancialDifficultyTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="ScheduleOfPaymentStatusOfFinancingReceivableModifiedPast12MonthsTableTextBlock" id="nbhc_ScheduleOfPaymentStatusOfFinancingReceivableModifiedPast12MonthsTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="ScheduleOfFinancialEffectOfLoanRestructuringModificationsTableTextBlock" id="nbhc_ScheduleOfFinancialEffectOfLoanRestructuringModificationsTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="FinancingReceivableModificationsTermOfExtension" id="nbhc_FinancingReceivableModificationsTermOfExtension" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="FinancingReceivableModificationsDelayedPaymentTerm" id="nbhc_FinancingReceivableModificationsDelayedPaymentTerm" type="xbrli:durationItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="ServicingAssetFeeIncome" id="nbhc_ServicingAssetFeeIncome" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="EquityMethodInvestmentUnrealizedGainLoss" id="nbhc_EquityMethodInvestmentUnrealizedGainLoss" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivableExcludingAccruedInterestPercent" id="nbhc_FinancingReceivableExcludingAccruedInterestPercent" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" />
  <xsd:element name="FinancingReceivableExcludingAccruedInterestModifiedSubsequentDefaultNumberOfLoans" id="nbhc_FinancingReceivableExcludingAccruedInterestModifiedSubsequentDefaultNumberOfLoans" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="OtherSecuritiesInvestmentsWithNoContractualMaturityMember" id="nbhc_OtherSecuritiesInvestmentsWithNoContractualMaturityMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="NbhHoldingsCorp.2023OmnibusIncentivePlanMember" id="nbhc_NbhHoldingsCorp.2023OmnibusIncentivePlanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="NewBoardAuthorizedShareRepurchaseProgram2021Member" id="nbhc_NewBoardAuthorizedShareRepurchaseProgram2021Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="PaymentsToAcquireEquitySecuritiesWithoutReadilyDeterminableFairValue" id="nbhc_PaymentsToAcquireEquitySecuritiesWithoutReadilyDeterminableFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="EquityMethodInvestmentsFairValueAndWithoutReadilyDeterminableFairValue" id="nbhc_EquityMethodInvestmentsFairValueAndWithoutReadilyDeterminableFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="EquityMethodInvestmentsWithoutReadilyDeterminableFairValueImpairmentLossAnnualAmount" id="nbhc_EquityMethodInvestmentsWithoutReadilyDeterminableFairValueImpairmentLossAnnualAmount" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="BusinessAcquisitionNumberOfBankingCentersAdded" id="nbhc_BusinessAcquisitionNumberOfBankingCentersAdded" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="OtherSecurities" id="nbhc_OtherSecurities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="DividendIncomeOtherSecuritiesOperating" id="nbhc_DividendIncomeOtherSecuritiesOperating" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="ProceedsFromSaleOfOtherSecurities" id="nbhc_ProceedsFromSaleOfOtherSecurities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="PaymentsToAcquireOtherSecurities" id="nbhc_PaymentsToAcquireOtherSecurities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="OtherSecuritiesAbstract" id="nbhc_OtherSecuritiesAbstract" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="OtherSecuritiesTextBlock" id="nbhc_OtherSecuritiesTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="ScheduleOfOtherSecuritiesTableTextBlock" id="nbhc_ScheduleOfOtherSecuritiesTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EquitySecuritiesWithReadilyDeterminableFairValuesMember" id="nbhc_EquitySecuritiesWithReadilyDeterminableFairValuesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="FundedAndUnfundedLoanCommitmentsMember" id="nbhc_FundedAndUnfundedLoanCommitmentsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="FundedLoanCommitmentsMember" id="nbhc_FundedLoanCommitmentsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="NetCashActivityFromAcquisition" id="nbhc_NetCashActivityFromAcquisition" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="LoansTransferredToOtherRealEstateOwnedAtFairValue" id="nbhc_LoansTransferredToOtherRealEstateOwnedAtFairValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="VistaBancsharesIncMember" id="nbhc_VistaBancsharesIncMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="DallasFt.WorthAustinAndLubbockRegionsMember" id="nbhc_DallasFt.WorthAustinAndLubbockRegionsMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="FixedToFloatingRateNote5.875PercentMaturing2036Member" id="nbhc_FixedToFloatingRateNote5.875PercentMaturing2036Member" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="AssociateStockPurchasePlanMember" id="nbhc_AssociateStockPurchasePlanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="RelativeTotalShareholderReturnPerformanceAdjustmentFactorPercentage" id="nbhc_RelativeTotalShareholderReturnPerformanceAdjustmentFactorPercentage" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="EarningsPerShareAndReturnOnTangibleAssetsPerformanceSharesMember" id="nbhc_EarningsPerShareAndReturnOnTangibleAssetsPerformanceSharesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="ScheduleOfLoansPurchasedInBusinessAcquisitionTableTextBlock" id="nbhc_ScheduleOfLoansPurchasedInBusinessAcquisitionTableTextBlock" type="dtr-types:textBlockItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="FinancingReceivablePurchasedSeasonedLoanAmountAtParValue" id="nbhc_FinancingReceivablePurchasedSeasonedLoanAmountAtParValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="FinancingReceivablePurchasedSeasonedLoanAllowanceForCreditLossAtAcquisitionDate" id="nbhc_FinancingReceivablePurchasedSeasonedLoanAllowanceForCreditLossAtAcquisitionDate" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivablePurchasedSeasonedLoanDiscountPremium" id="nbhc_FinancingReceivablePurchasedSeasonedLoanDiscountPremium" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivablePurchasedSeasonedLoanAmountAtPurchasePrice" id="nbhc_FinancingReceivablePurchasedSeasonedLoanAmountAtPurchasePrice" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="FinancingReceivablePurchasedLoanAmountAtParValue" id="nbhc_FinancingReceivablePurchasedLoanAmountAtParValue" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="FinancingReceivablePurchasedLoanAllowanceForCreditLossAtAcquisitionDate" id="nbhc_FinancingReceivablePurchasedLoanAllowanceForCreditLossAtAcquisitionDate" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivablePurchasedLoanDiscountPremium" id="nbhc_FinancingReceivablePurchasedLoanDiscountPremium" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivablePurchasedLoanAmountAtPurchasePrice" id="nbhc_FinancingReceivablePurchasedLoanAmountAtPurchasePrice" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="BusinessCombinationProFormaInformationNonrecurringAdjustmentEstimatedNetAccretionOfLoanAndInvestmentMember" id="nbhc_BusinessCombinationProFormaInformationNonrecurringAdjustmentEstimatedNetAccretionOfLoanAndInvestmentMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="BusinessCombinationProFormaInformationNonrecurringAdjustmentEstimatedAmortizationOfAcquiredIntangiblesMember" id="nbhc_BusinessCombinationProFormaInformationNonrecurringAdjustmentEstimatedAmortizationOfAcquiredIntangiblesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="VistaEquityPlanMember" id="nbhc_VistaEquityPlanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="InducementPlanMember" id="nbhc_InducementPlanMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="NumberOfBankingCentersApprovedForConsolidation" id="nbhc_NumberOfBankingCentersApprovedForConsolidation" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="LongLivedAssetsHeldForSale" id="nbhc_LongLivedAssetsHeldForSale" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="instant" abstract="false" xbrli:balance="debit" />
  <xsd:element name="NetPaymentsToAdvancesFromFederalHomeLoanBank" id="nbhc_NetPaymentsToAdvancesFromFederalHomeLoanBank" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="BasisOfPresentationTable" id="nbhc_BasisOfPresentationTable" type="xbrli:stringItemType" substitutionGroup="xbrldt:hypercubeItem" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="BasisOfPresentationLineItems" id="nbhc_BasisOfPresentationLineItems" type="xbrli:stringItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="DebtSecuritiesAvailableForSaleExcludingAccruedInterestAcquiredFromBusinessCombinations" id="nbhc_DebtSecuritiesAvailableForSaleExcludingAccruedInterestAcquiredFromBusinessCombinations" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="FederalHomeLoanBankLoanPrepaymentPenalty" id="nbhc_FederalHomeLoanBankLoanPrepaymentPenalty" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardPerformanceConditionAdjustmentFactorPercentage" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardPerformanceConditionAdjustmentFactorPercentage" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="TimeBasedRestrictedStockMember" id="nbhc_TimeBasedRestrictedStockMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="PerformanceBasedRestrictedStockMember" id="nbhc_PerformanceBasedRestrictedStockMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="IntegrationOrRebrandingConditionMember" id="nbhc_IntegrationOrRebrandingConditionMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="ShareBasedCompensationArrangementByShareBasedPaymentAwardPerformanceConditionWeightingPercentage" id="nbhc_ShareBasedCompensationArrangementByShareBasedPaymentAwardPerformanceConditionWeightingPercentage" type="dtr-types:percentItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="CostSavingsConditionMember" id="nbhc_CostSavingsConditionMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="ShareBasedCompensationArrangementVestingNumberOfQuarterlyInstallments" id="nbhc_ShareBasedCompensationArrangementVestingNumberOfQuarterlyInstallments" type="xbrli:integerItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" />
  <xsd:element name="VistaSecuritiesMember" id="nbhc_VistaSecuritiesMember" type="dtr-types:domainItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="true" />
  <xsd:element name="ProceedsFromSaleAndMaturityOfOtherSecurities" id="nbhc_ProceedsFromSaleAndMaturityOfOtherSecurities" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="debit" />
  <xsd:element name="BusinessCombinationConsiderationTransferredAmountOfPreacquisitionDebtInAcquireeSettledUponClosing" id="nbhc_BusinessCombinationConsiderationTransferredAmountOfPreacquisitionDebtInAcquireeSettledUponClosing" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="BusinessCombinationConsiderationTransferredIncludingSettlementOfPreExistingDebt" id="nbhc_BusinessCombinationConsiderationTransferredIncludingSettlementOfPreExistingDebt" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
  <xsd:element name="FinancingReceivableExcludingAccruedInterestAllowanceForCreditLossIncreaseDecreaseOnAcquisition" id="nbhc_FinancingReceivableExcludingAccruedInterestAllowanceForCreditLossIncreaseDecreaseOnAcquisition" type="xbrli:monetaryItemType" substitutionGroup="xbrli:item" nillable="true" xbrli:periodType="duration" abstract="false" xbrli:balance="credit" />
</xsd:schema>
