Exhibit 99.2

NBH Bank, N.A. to Convert to Colorado State Charter

Company Release – November 4, 2015

GREENWOOD VILLAGE, Colo.--(PR Newswire)-- National Bank Holdings Corporation (NYSE: NBHC) today announced that its subsidiary, NBH Bank,  N.A. (the “Bank”), filed an application with the Colorado Division of Banking (the “DOB”) to convert from a national association to a Colorado state-chartered bank, and also filed a notice of the charter conversion with its current primary federal regulator, the Office of the Comptroller of the Currency. The Bank is also in the process of filing an application with the Federal Reserve Bank of Kansas City to remain a member bank of the Federal Reserve System following the charter conversion.

As a result of the conversion, the DOB will be the Bank’s primary regulator and the Federal Reserve Bank of Kansas City will be the Bank’s primary federal regulator. Regulatory approval is expected before year-end. Upon conversion, NBH Bank, N.A. will change its name to NBH Bank, but each of the Bank’s brand names (Bank Midwest, Community Banks of Colorado and Hillcrest Bank) will stay the same. The conversion is not expected to affect the Bank’s clients in any way, and they will continue to receive the same protection on deposits through the FDIC.

About National Bank Holdings Corporation 

National Bank Holdings Corporation is a bank holding company created to build a leading community bank franchise delivering high quality client service and committed to shareholder results. National Bank Holdings Corporation operates a network of 97 banking centers located in Colorado, the greater Kansas City region and Texas. Through the Company’s subsidiary, NBH Bank, N.A., it operates under the following brand names: Bank Midwest in Kansas and Missouri, Community Banks of Colorado in Colorado, and Hillcrest Bank in Texas. More information about National Bank Holdings Corporation can be found at www.nationalbankholdings.com.

Forward-Looking Statements

This press release contains “forward-looking statements” within the meaning of the Private Securities Litigation Reform Act of 1995. Forward-looking statements contain words such as “anticipate,” “believe,” “can,” “would,” “should,” “could,” “may,” “predict,” “seek,” “potential,” “will,” “estimate,” “target,” “plan,” “project,” “continuing,” “ongoing,” “expect,” “intend” or similar expressions that relate to the Company’s strategy, plans or intentions. Forward-looking statements involve certain important risks, uncertainties and other factors, any of which could cause actual results to differ materially from those in such statements. Such factors include, without limitation, the risk that the applications discussed above are not approved or that the process of converting charters will have unexpected costs or other consequences, the “Risk Factors” referenced in the Company’s most recent Form 10-K filed with the Securities and Exchange Commission (SEC), other risks and uncertainties listed from time to time in our reports and documents filed with the SEC. The Company can give no assurance that any goal or plan or expectation set forth in forward-looking

statements can be achieved and readers are cautioned not to place undue reliance on such statements. The forward-looking statements are made as of the date of this press release, and the Company does not intend, and assumes no obligation, to update any forward-looking statement to reflect events or circumstances after the date on which the statement is made or to reflect the occurrence of unanticipated events or circumstances, except as required by applicable law.

Contact: