Exhibit 5.1

Squire Patton Boggs (US) LLP 

201 E. Fourth St., Suite 1900

Cincinnati, Ohio 45202

O     +1 513 361 1200 

F      +1 513 361 1201 

squirepattonboggs.com

September 1, 2022

RE: Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to National Bank Holdings Corporation, a Delaware corporation (the “Company”), in connection with the automatic shelf registration statement on Form S-3 (the “Registration Statement”) filed on the date hereof by the Company with the Securities and Exchange Commission (the “SEC”) under the Securities Act of 1933, as amended (including the rules and regulations thereunder, the “Securities Act”).  The Registration Statement relates to, among other things, the offer and sale from time to time, pursuant to Rule 415 of the General Rules and Regulations promulgated under the Act, of the following securities of the Company: (a) debt securities (the “Debt Securities”),  which, unless otherwise provided in any supplement to the prospectus forming a part of the Registration Statement relating to a particular series of the Debt Securities, may be in the form of senior debt securities or subordinated debt securities; (b) shares of Class A common stock, par value $0.01 per share, and Class B non-voting common stock, $0.01 par value per share (the “Common Stock”); (c) preferred stock, par value $0.01 per share (the “Preferred Stock”); (d) depositary shares representing a fraction of a share of a particular class or series of the Preferred Stock (“Depositary Shares”); (e) contracts for the purchase and sale of securities registered under the Registration Statement (the “Purchase Contracts”); (f) warrants to purchase other securities registered under the Registration Statement (the “Warrants”); (g) rights representing rights to purchase securities registered under the Registration Statement (the “Rights”); and (h) units representing an interest in two or more securities registered under the Registration Statement (the “Units”).  The foregoing items (a) though (h) are referred to herein as the “Securities.”

The Debt Securities are to be issued under an Indenture (the “Indenture”), between the Company and U.S. Bank Trust Company, National Association, as trustee, a form of which has been filed as Exhibit 4.2 (in the case of senior Debt Securities) or Exhibit 4.3 (in the case of subordinated Debt Securities) to the Registration Statement.  The Purchase Contracts are to be issued pursuant to a purchase contract agreement (the “Purchase Contract Agreement”) between the Company and the purchase contract agent to be named therein.  The Warrants are to be issued from time to time under one or more warrant agreements (each, a “Warrant Agreement”), each to be entered into by the Company and one or more institutions, as warrant agents, each as identified in the applicable Warrant Agreement.  The Rights are to be issued pursuant to a rights agreement (the “Rights Agreement”) between the Company and the agent to be named therein.  The Units are to be issued pursuant to a unit certificate or other applicable agreement (the “Unit Agreement”) between the Company and the agent to be named therein.

The prospectus that is part of the Registration Statement as supplemented in the future by various supplements to the prospectus (each, a “Prospectus Supplement”) will provide for the issuance and sale by the Company of the Securities, which may be offered pursuant to Rule 415 under the Securities Act.

45 Offices in 20 Countries

Squire Patton Boggs (US) LLP is part of the international legal practice Squire Patton Boggs, which operates worldwide through a number of separate legal entities.

Please visit squirepattonboggs.com for more information.

Squire Patton Boggs (US) LLP

RE: Registration Statement on Form S-3

September 1, 2022

Page 2

In rendering the opinions stated herein, we have examined and relied upon the following: (a) the Registration Statement; (b) the forms of the Senior Indenture and the Subordinated Indenture, both of which are being filed as exhibits to the Registration Statement; (c) the Second Amended and Restated Certificate of Incorporation of the Company; (d) the Second Amended and Restated Bylaws of the Company, as in effect as of the date hereof; and (e) a copy of certain resolutions of the Board of Directors of the Company relating to the registration of the Securities.

We have examined and relied on originals or copies certified or otherwise identified to our satisfaction of such documents, corporate records, certificates of the Company or public officials and other instruments as we have deemed necessary or appropriate for the purposes of this opinion letter.  In such examination, we have assumed (a) the authenticity of original documents and the genuineness of all signatures; (b) the conformity to the originals of all documents submitted to us as copies; (c) the truth, accuracy and completeness of the information, representations and warranties contained in the agreements, records, documents, instruments and certificates we have reviewed; (d) the Registration Statement, and any amendments thereto (including post-effective amendments), are effective under the Securities Act; (e) a Prospectus Supplement will have been filed with the SEC describing the Securities offered thereby; (f) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and the applicable Prospectus Supplement(s); (g) a definitive purchase, underwriting, agency or similar agreement with respect to any Securities offered (each, a “purchase agreement”) will have been duly authorized and validly executed and delivered by the parties thereto; (h) any Debt Securities that may be issued will be issued in a form that complies with the Indenture, and any supplemental indenture to be entered into in connection with the issuance of such Debt Securities will be manually signed or countersigned, as the case may be, by duly authorized officers of the Company and of the trustee named therein, and any Warrants, Purchase Contracts, Rights or Units that may be issued will be a form that complies with the applicable agreement described above; and (i) at the time of any issuance of Common Stock or the Securities convertible into, exchangeable, redeemable or exercisable for Common Stock, there will be sufficient authorized but unissued shares of Common Stock reserved for such issuance and any Securities issuable upon conversion, exchange, redemption or exercise of any Securities being offered will be duly authorized and created.  We have assumed that the terms of the Securities have been duly authorized and created by the Company, and that the terms of the Securities have been established so as not to, and that the execution and delivery by the parties thereto of the documents pursuant to which the Securities are governed and the performance of such parties’ obligations thereunder, will not, breach, violate, conflict with or constitute a default under (1) the organizational documents of any party or any agreement or instrument to which any party thereto is subject, (2) any law, rule or regulation to which any party thereto is subject and the federal securities laws of the United States of America as such laws apply to the Company and the transaction pursuant to which the Securities are offered, (3) any judicial or regulatory order or decree of any governmental authority or (4) any consent, approval, license, authorization or validation of, or filing, recording or registration with, any governmental authority.  We also assume that at the time of issuance of the Securities the Company is and will remain duly organized, validly existing and in good standing under the laws of the State of Delaware and that the Company will have duly authorized the issuance of the Securities and related matters.  As to any facts material to the opinions expressed herein that we did not independently establish or verify, we have relied and will rely upon statements and representations of officers and other representatives of the Company and others.

We are members of the Bar of the State of New York, and we have not considered, and we express no opinion as to, the laws of any jurisdiction other than the laws of the State of New York and the federal securities laws (excluding antifraud laws) of the United States of America, in each case as in effect on the date hereof.  We have assumed that the Securities and the agreements governing the terms thereof will be governed by the laws of the State of New York.

Squire Patton Boggs (US) LLP

RE: Registration Statement on Form S-3

September 1, 2022

Page 3

Based upon the foregoing, and subject to the qualifications set forth in this letter, we advise you that, in our opinion:

1. With respect to any shares of Common Stock offered by the Company (the “Offered Common Stock”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Common Stock has been prepared, delivered and filed in compliance with the Securities Act; (b) terms of the issuance and sale of the Offered Common Stock have been duly established and are then in conformity with the Certificate of Incorporation and the Bylaws so as not to violate any applicable law, the Certificate of Incorporation or the Bylaws or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or other governmental authority having jurisdiction over the Company; (c) if the Offered Common Stock is to be certificated, certificates in the form required under Delaware corporate law representing the shares of Offered Common Stock have been duly executed and countersigned and (d) the shares of Common Stock are registered in the Company’s share registry and delivered upon payment of the agreed-upon consideration therefor, the shares of Offered Common Stock, when issued and sold or otherwise distributed in accordance with the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding agreement, will be duly authorized and validly issued, and the shares of Offered Common Stock, when issued and sold or otherwise distributed in accordance with the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding agreement, will be fully paid and nonassessable, in each case provided that the consideration therefor is not less than $0.01 per share of Common Stock.

2. With respect to the shares of any series of Preferred Stock offered by the Company (the “Offered Preferred Stock”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Preferred Stock has been prepared, delivered and filed in compliance with the Securities Act; (b) a Certificate of Designations for the Offered Preferred Stock in accordance with the applicable provisions of Delaware corporate law (the “Certificate of Designations”) has been filed with, and accepted for record by, the Secretary of State of the State of Delaware, in the form to be filed as an exhibit to a post-effective amendment to the Registration Statement or as an exhibit to a Current Report on Form 8-K or other applicable report under the Securities Exchange Act of 1934, as amended, in the manner contemplated in the Registration Statement or any prospectus supplement relating thereto; (c) the terms of the Offered Preferred Stock and of their issuance and sale have been duly established and are then in conformity with the Certificate of Incorporation, including the Certificate of Designations relating to the Offered Preferred Stock, and the Bylaws so as not to violate any applicable law, the Certificate of Incorporation or the Bylaws or result in a default under or breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or other governmental authority having jurisdiction over the Company; (d) if the Offered Preferred Stock is to be certificated, certificates in the form required under Delaware corporate law representing the shares of Offered Preferred Stock have been duly executed and countersigned and (e) the shares of Offered Preferred Stock are registered in the Company’s share registry and delivered upon payment of the agreed-upon consideration therefor, the shares of Offered Preferred Stock, when issued and sold or otherwise distributed in accordance with the applicable underwriting agreement, if any, or any other duly authorized, executed and delivered valid and binding agreement, will be duly authorized, validly issued, fully paid and nonassessable, provided that the consideration therefor is not less than $0.01 per share of Preferred Stock.

3. With respect to any series of Debt Securities to be offered by the Company pursuant to the Registration Statement (the “Offered Debt Securities”), when (a) the Indenture has been qualified under the Trust Indenture Act of 1939, as amended; (b) an appropriate Prospectus Supplement or term sheet with respect to the Offered Debt Securities has been prepared, delivered and filed in compliance with the Securities Act; (c) the Indenture and any supplemental indenture in respect of such Offered Debt Securities have been duly authorized, executed and delivered by each party thereto; (d) the terms of the Offered Debt Securities and of their issuance and sale have been duly established in conformity with the Indenture and any supplemental indenture to be entered into in connection with the issuance of such Offered Debt Securities; and (e) the Offered Debt Securities have been duly authorized, executed and delivered against payment of the agreed-upon consideration therefor, the Offered Debt Securities (including any Debt Securities duly issued upon conversion, exchange or exercise of any Securities) when issued and sold in accordance with the Indenture, any supplemental indenture to be entered into in connection with the issuance of such Offered Debt Securities and the applicable purchase agreement, will be valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

Squire Patton Boggs (US) LLP

RE: Registration Statement on Form S-3

September 1, 2022

Page 4

4. With respect to any Purchase Contracts to be offered by the Company pursuant to the Registration Statement (the “Offered Purchase Contracts”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Purchase Contracts has been prepared, delivered and filed in compliance with the Securities Act; (b) the terms of the issuance and sale of the Purchase Contract Agreement have been duly established in conformity with the Offered Purchase Contracts; and (c) the Offered Purchase Contracts have been duly executed and delivered against payment therefor, the Offered Purchase Contracts, when issued and sold in accordance with the applicable purchase agreement, will be valid and legally binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

5. With respect to any Warrants to be offered by the Company pursuant to the Registration Statement (the “Offered Warrants”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Warrants has been prepared, delivered and filed in compliance with the Securities Act; (b) the applicable Warrant Agreement has been duly authorized, executed and delivered by the parties thereto; (c) the terms of the issuance and sale of the Offered Warrants have been duly established in conformity with the applicable Warrant Agreement; and (d) the Offered Warrants have been duly authorized, executed and delivered against payment therefor, the Offered Warrants, when issued and sold in accordance with the applicable purchase agreement, will be valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

6. With respect to any Rights to be offered by the Company pursuant to the Registration Statement (the “Offered Rights”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Rights has been prepared, delivered and filed in compliance with the Securities Act; (b) the terms of the issuance and sale of the Rights Agreement have been duly established in conformity with the Offered Rights; and (c) the Offered Rights have been duly executed and delivered against payment therefor, the Offered Rights, when issued and sold in accordance with the applicable purchase agreement, will be valid and legally binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

7. With respect to any Units to be offered by the Company pursuant to the Registration Statement (the “Offered Units”), when (a) an appropriate Prospectus Supplement or term sheet with respect to the Offered Units has been prepared, delivered and filed in compliance with the Securities Act; (b) the terms of the issuance and sale of the Offered Units have been duly established in conformity with the Unit Agreement; (c) any shares of Common Stock that are a component of any Offered Units are validly issued, fully paid and nonassessable and any other Securities that are components of any Offered Units are valid and binding obligations of the Company, enforceable against the Company in accordance with their respective terms; and (d) the Offered Units have been duly executed and delivered pursuant to the Unit Agreement, the Units, when issued and sold in accordance with the applicable purchase agreement, will be valid and legally binding obligations of the Company, enforceable against the Company in accordance with their respective terms.

The opinions set forth above are subject to the effects of (a) bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar laws relating to or affecting the enforcement of creditors’ rights generally; (b) general equitable principles (whether considered in a proceeding in equity or at law); (c) an implied covenant of good faith and fair dealing; (d) provisions of law that require that a judgment for money damages rendered by a court in the United States be expressed only in United States dollars; (e) limitations by any governmental authority that limit, delay or prohibit the making of payments outside the United States; and (f) generally applicable laws that (1) provide for the enforcement of oral waivers or modifications where a material change of position in reliance thereon has occurred or provide that a course of performance may operate as a waiver, (2) limit the availability of a remedy under certain circumstances where another remedy has been elected, (3) limit the enforceability of provisions releasing, exculpating or exempting a party from, or requiring indemnification of a party for, liability for its own action or inaction, to the extent the action or inaction involves negligence, gross negligence, recklessness, willful misconduct or unlawful conduct, (4) may, where less than all of a contract may be unenforceable, limit the enforceability of the balance of the contract to circumstances in which the unenforceable portion is not an essential part of the agreed-upon exchange, (5) may limit the enforceability of provisions providing for compounded interest, imposing increased interest rates or late payment charges upon delinquency in payment or default or providing for liquidated damages or for premiums or penalties upon acceleration, or (6) limit the waiver of rights under usury laws.  Furthermore, the manner in which any particular issue relating to the opinions would be treated in any actual court case would depend in part on facts and circumstances particular to the case and would also depend on how the court involved chose to exercise the wide discretionary authority generally available to it.  We express no opinion as to the effect of Section 210(p) of the Dodd-Frank Wall Street Reform and Consumer Protection Act.

Squire Patton Boggs (US) LLP

RE: Registration Statement on Form S-3

September 1, 2022

Page 5

We express no opinion as to whether, or the extent to which, the laws of any particular jurisdiction apply to the subject matter hereof, including, without limitation, the enforceability of the governing law provision contained in any Securities and their governing documents.

This letter speaks only as of its date and is delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.  We hereby consent to the filing of copies of this opinion letter as an exhibit to the Registration Statement and to the use of our name in the prospectus forming a part of the Registration Statement under the caption “Legal Matters.”  In giving this consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act.

Respectfully Submitted,

/s/ Squire Patton Boggs (US) LLP