Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in the Registration Statement (No. 333-204071) on Form S-8 of National Bank Holdings Corporation of our report dated May 29, 2024 with respect to the statement of financial condition of the National Bank Holdings Corporation Employee Stock Purchase Plan as of February 29, 2024, and the related statement of income and changes in plan equity for the year ended February 29, 2024.

/s/ Mayer Hoffman McCann P.C.

Kansas City, Missouri

May 29, 2024