Exhibit 5.1

[Wachtell, Lipton, Rosen & Katz Letterhead]

May 9, 2023

National Bank Holdings Corporation
7800 East Orchard, Suite 300
Greenwood Village, Colorado 80111

Ladies and Gentlemen:

We have acted as special counsel to National Bank Holdings Corporation, a Delaware corporation (the “Company”) in connection with the Registration Statement on Form S-8 (the “Registration Statement”, which term does not include any other document or agreement whether or not specifically referred to therein or attached as an exhibit or schedule thereto) under the Securities Act of 1933, as amended (the “Act”), relating to the issuance by the Company of up to 1,739,516 shares of Class A common stock, par value $0.01 per share, of the Company (the “Shares”), which may be issued pursuant to the National Bank Holdings Corporation 2023 Omnibus Incentive Plan (the “Plan”). In connection with the foregoing, you have requested our opinion with respect to the following matters.

In our capacity as special counsel to the Company and in connection with the opinion set forth herein, we have examined the originals, or duplicates or certified or conformed copies, of such corporate records, agreements, documents and other instruments, including the amended and restated certificate of incorporation and bylaws of the Company, and have made such other investigations as we have deemed relevant and necessary in connection with the opinion set forth below. As to questions of fact material to this opinion that have not been independently established, we have relied, with your approval, and without independent verification, upon oral and written representations of officers and representatives of the Company and certificates or comparable documents of public officials and of officers and representatives of the Company.

In making such examination and rendering this opinion, we have assumed, with your approval and without independent verification, the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of documents submitted to us as certified, facsimile, conformed, electronic or photostatic copies and the authenticity of the originals of such copies. We have relied, to the extent we deem appropriate, on guidance of the Securities and Exchange Commission (including the Staff thereof).

In rendering the opinion set forth below, we have also assumed that the Shares, when issued, will be duly authenticated by the transfer agent and registrar for the Shares and that the certificates, if any, evidencing the Shares to be issued will be manually signed by one of the authorized officers of the transfer agent and registrar for the Shares and registered by such transfer agent and registrar and will conform to the specimen certificate examined by us evidencing the Shares.

Based upon the foregoing, and subject to the assumptions, exceptions, limitations, qualifications and comments stated herein, we are of the opinion that when the Shares have been issued in accordance with the provisions of the Plan, the Shares will be validly issued, duly authorized, fully paid and nonassessable.

This opinion letter is issued to you solely for use in connection with the Registration Statement and is not to be quoted or otherwise referred to in any financial statements of the Company or any other document, nor is it to be filed with or furnished to any government agency or other person, without our prior written consent.

We are members of the bar of the State of New York, and we do not express any opinion herein concerning any law other than the Delaware General Corporation Law (including the statutory provisions, all applicable provisions of the Delaware Constitution and reported judicial decisions interpreting the foregoing). This opinion is given on the basis of the law and the facts existing as of the date hereof. This opinion speaks only as of its date and we assume no obligation to advise you of changes in matters of fact or law which may thereafter occur.

We hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement. In giving such consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act, and the rules and regulations of the SEC promulgated thereunder.

Very truly yours,

/s/ Wachtell, Lipton, Rosen & Katz

-2-