TRANSITION AND CONSULTING AGREEMENT

THIS TRANSITION AND CONSULTING AGREEMENT (this “Agreement”) dated as of April 7, 2014 is by and among NBH Bank, N.A. (the “Bank”), National Bank Holdings Corporation (either individually or together with the Bank, the “Company”), and Donald Gaiter (“Consultant”).

WHEREAS, Consultant has extensive experience and knowledge, including with the Bank and the Company, relating to corporate strategy and the acquisition of financial institutions;

WHEREAS, the parties acknowledge that Consultant has informed the Company of his intention to continue to be employed through April 30, 2014 (the “Transition Date”) and terminate his employment with the Company and his position as Chief of Acquisitions and Strategy on the Transition Date;

WHEREAS, the parties further acknowledge that such termination on the Transition Date shall not be deemed to be a Termination of Service (as defined in the Company’s 2009 Equity Incentive Plan);

WHEREAS, if Consultant’s employment terminates prior to the Transition Date for any reason, the Transition Date shall not occur and this Agreement shall be void ab initio; and

WHEREAS, the Company wishes to continue to retain the services of Consultant following the Transition Date, on a part-time, advisory, independent contractor basis, on the terms and conditions set forth herein, and Consultant has agreed to so serve the Company and its affiliates in such role following the Transition Date.

NOW, THEREFORE, in consideration of the foregoing, of the mutual promises contained herein and of other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the parties hereto hereby agree as follows:

1.Term. The Company shall retain Consultant pursuant to the terms of this Agreement, and Consultant shall provide the Services (as defined below), for a term commencing on May 1, 2014 and ending on October 31, 2014 or upon the earlier termination of this Agreement in accordance with Section 5 hereof (the “Term”).

2.Services. During the Term, Consultant shall serve the Company in the role of “M&A Advisor,” and shall report directly to the President & Chief Executive Officer of the Company and shall provide services (the “Services”) at the reasonable request of the President & Chief Executive Officer of the Company.

3.Compensation.

(a)Consulting Retainer. During the Term, Consultant shall receive a monthly retainer, payable on the first business day of the applicable month in arrears (the “Retainer”) at a rate of $2,000.00 per month.

(b)Rate. During the Term, for each day that Consultant provides Services for the Company, he shall receive a maximum per diem equal to $1,345.00 (the “Per Diem”), with any fractions of a day calculated at the hourly rate equivalent to the stated Per Diem rate divided by eight

hours. Consultant shall provide the Company with an invoice once a month outlining the days and related hours that he provided Services and the nature of such Services; provided, however, that the Company shall only be required to pay any such Per Diems to the extent such amount exceeds the cumulatively paid Retainers. The Company shall pay approved invoices no later than the 15^th day following the approval of such invoice, with such approval not to be unreasonably withheld or delayed.

(c)Reimbursement for Business Expenses. Upon presentation of appropriate documentation, Consultant shall be reimbursed, in accordance with the Company’s expense reimbursement policy, for all reasonable business expenses incurred in connection with Consultant’s performance of the Services.

4.Independent Contractor Status. Consultant acknowledges and agrees that Consultant’s status at all times shall be that of an independent contractor, and that Consultant may not, at any time, act as a representative for or on behalf of the Company for any purpose or transaction, and may not bind or otherwise obligate the Company in any manner whatsoever other than at the written request of the Company. The parties hereby acknowledge and agree that all Retainers and Per Diems paid pursuant to Section 3 hereof shall represent fees for services as an independent contractor, and shall therefor be paid without any deductions or withholdings taken therefrom for taxes or for any other purpose. Consultant further acknowledges that the Company makes no warranties as to any tax consequences regarding payment of such fees, and specifically agrees that the determination of any tax liability or other consequences of any payment made hereunder is Consultant’s sole and complete responsibility and that Consultant will pay all taxes, if any, assessed on such payments under the applicable laws of any Federal, state, local or other jurisdiction and, to the extent not so paid, will indemnify the Company for any taxes so assessed against the Company. Consultant also agrees that during the Term, Consultant shall not be eligible to participate in any of the employee benefit plans or arrangements of the Company.

5.Termination.

(a)The Company may terminate this Agreement at any time and for any reason (or no reason) by providing written notice to Consultant of such termination and the effective date thereof (the date of termination of this Agreement, the “Termination Date”).

(b)Consultant may terminate this Agreement at any time and for any reason (or no reason) by providing written notice of such termination and the Termination Date to the Company no less than 15 days prior to the Termination Date.

(c)For purposes of (i) each Option Award Agreement entered into by Consultant and the Company that provides for the grant of stock options to acquire Company common stock to Consultant and (ii) the Restricted Stock Award Agreement, dated as of October 11, 2011, any Termination of Service (as defined in the Company’s 2009 Equity Incentive Plan) following the Transition Date, including a termination pursuant to Section 5(a) or 5(b) above and the expiration of the Term, shall be deemed to be a Termination of Service without Cause.

(d)Termination Payment.

(i)In the event of a termination of this Agreement in accordance with Section 5, the Company shall have no further obligation to Consultant following the Termination Date other than to pay to Consultant, within 30 days following the Termination Date, an amount equal to (A) only if Consultant has not yet been paid his Retainer for the calendar month in which the Termination Date occurs, the Retainer, multiplied by a fraction, the numerator of

which is the number of days from and including the first day of such calendar month through the Termination Date, and the denominator of which is the total number of days in the applicable month, such payment to be made on the date payment in respect of such calendar month would have been made had such termination not occurred, (B) any unpaid Per Diems (subject to the proviso in Section 3(b)) and (C) any unreimbursed reasonable business expenses incurred prior the Termination Date in connection with Consultant’s performance of Services hereunder that are documented in accordance with the Company’s expense reimbursement policy.

(ii)Other than payments or benefits required to be paid or provided or which Consultant is eligible to receive under any plan, program, policy or practice or contract of agreement of the Company or any of its affiliated entities through the date of termination, the payments and benefits provided under this Section 5 shall be in full satisfaction of the Company’s obligations to Consultant upon his termination of employment, notwithstanding the remaining length of the Term, and in no event shall Consultant be entitled to any other benefits (including severance or any other damages in respect of a termination of the consulting relationship or claim for breach of this Agreement) beyond those specified in this Section 5.

6.Restrictive Covenants.

(a)Return of Bank and Company Property. Upon the end of the Term, Consultant shall promptly return to the Company any keys, credit cards, passes, confidential documents or material, or other property belonging to the Bank or the Company, and Consultant shall also return all writings, files, records, correspondence, notebooks, notes and other documents and things (including any copies thereof) containing confidential information or relating to the business or proposed business of the Company or any of its affiliated entities or containing any trade secrets relating to the Company or its affiliated entities except any personal diaries, calendars, rolodexes or personal notes or correspondence. For purposes of the preceding sentence, the term “trade secrets” shall have the meaning ascribed to it under the Uniform Trade Secrets Act. Consultant agrees to represent in writing to the Company upon Termination of Services that he has complied with the foregoing provisions of this Section 6(a).

(b)Mutual Nondisparagement. Consultant and the Company each agree that, following during and after the Term, neither Consultant, nor the Company will make any public statements which materially disparage the other party. Notwithstanding the foregoing, nothing in this Section 6(b) shall prohibit any person from making truthful statements when required by order of a court or other governmental or regulatory body having jurisdiction or to enforce any legal right including, without limitation, the terms of this Agreement.

(c)Confidential Information. Consultant agrees that, during his employment with the Bank or the Company, while providing consulting Services to the Bank or the Company and at all times thereafter, he shall hold for the benefit of the Company all secret or confidential information, knowledge or data relating to the Company or any its affiliated entities, and their respective businesses, which shall have been obtained by Consultant during Consultant’s employment by the Company or during his consultation with the Company, and which shall not be or become public knowledge (other than by acts by Consultant or representatives of Consultant in violation of this Agreement). Except in the good faith performance of his duties for the Company, Consultant shall not, without the prior written consent of the Company or as may otherwise be required by law or legal process, communicate or divulge any such information, knowledge or data to anyone other than the Company and those designated by it.

(d)Nonsolicitation. Consultant agrees that, while he is providing Services to the Bank or the Company and during the one-year period following the end of the Term, Consultant shall not, in any manner, directly or indirectly, (i) solicit or induce, or attempt to solicit or induce, any individual who is, on the Termination Date (or was, during the six-month period prior to the Termination Date), employed by the Company or its affiliated entities to terminate or refrain from renewing or extending such employment or to become employed by or become a consultant to any other individual or entity other than the Company or its affiliated entities, (ii) initiate discussions with any such employee or former employee for any such purpose or authorize or knowingly cooperate with the taking of any such actions by any other individual or entity on behalf of Consultant’s employer or (iii) solicit or induce, or attempt to solicit or induce, any client, customer or investor (in each case, whether former, current or prospective), supplier, licensee or other business relation of the Company or any of its affiliated entities to cease, or reduce or refrain from, doing business with the Company or such affiliated entity, or in any way interfere with or damage the relationship between any such client, customer, investor, supplier, licensee or business relation, on the one hand, and the Company or any of its affiliated entities, on the other hand.

(e)Equitable Remedies. Consultant acknowledges that the Company would be irreparably injured by a violation of Section 6(b), (c) or (d) and he agrees that the Company, in addition to any other remedies available to it for such breach or threatened breach, on meeting the standards required by law, shall be entitled to a preliminary injunction, temporary restraining order, or other equivalent relief, restraining Consultant from any actual or threatened breach of Section 6(b), (c) or (d). If a bond is required to be posted in order for the Company to secure an injunction or other equitable remedy, the parties agree that said bond need not be more than a nominal sum.

(f)Severability; Blue Pencil. Consultant acknowledges and agrees that he has had the opportunity to seek advice of counsel in connection with the Agreement and the restrictive covenants contained herein are reasonable in scope, temporal duration, and in all other respects. If it is determined that any provision of this Section 6 is invalid or unenforceable, the remainder of the provisions of this Section 6 shall not thereby be affected and shall be given full effect, without regard to the invalid portions. If any court or other decision-maker of competent jurisdiction determines that any of the provisions in this Section 6 are unenforceable because of the duration or scope of such provision, then after such determination becomes final and unappealable, the duration or scope of such provision, as the case may be, shall be reduced so that such provision becomes enforceable, and in its reduced form, such provision shall be enforced.

7.Consultant Representations. Consultant hereby represents and warrants to the Company that the execution, delivery and performance of this Agreement by Consultant does not and will not conflict with, breach, violate or cause a default under (i) any agreement, contract or instrument to which Consultant is a party, including, but not limited to, any employment, consulting, noncompetition, nonsolicitation, confidentiality or similar agreement or arrangement, or (ii) any judgment, order or decree to which Consultant is subject. Consultant acknowledges and understands that the Company has relied on the foregoing representations in entering into this Agreement.

8.Cooperation. Consultant will fully cooperate with the Company and take reasonable steps necessary to ensure a smooth transition of Consultant’s current job duties and responsibilities as requested by the Company.

9.Governing Law. The provisions of this Agreement shall be construed in accordance with the internal laws of the State of Delaware, without regard to the conflict of law provisions of any state.

10.Dispute Resolution. Any controversy or claim arising out of or relating to this Agreement or the breach of this Agreement (other than a controversy or claim arising under Section 6 of this Agreement) that is not resolved by Consultant and the Company shall be submitted to confidential arbitration in a location selected by the Company in accordance with Delaware law and the procedures of the American Arbitration Association. The determination of the arbitrator shall be conclusive and binding on the Bank or the Company and Consultant and judgment may be entered on the arbitrator(s)’ awards in any court having competent jurisdiction.

11.Successors.

(a)This Agreement is personal to Consultant and without the prior written consent of the Company shall not be assignable by Consultant. This Agreement and any rights and benefits hereunder shall inure to the benefit of and be enforceable by Consultant’s legal representatives, heirs or legatees. This Agreement and any rights and benefits hereunder shall inure to the benefit of and be binding upon the Company and its successors and assigns.

(b)The Bank and the Company will require any successor (whether direct or indirect, by purchase, merger, consolidation or otherwise) to all or substantially all of the business and/or assets of the Bank and/or the Company to assume expressly and agree to satisfy all of the obligations under this Agreement in the same manner and to the same extent that the Company would be required to satisfy such obligations if no such succession had taken place. As used in this Agreement, “Company” shall mean the Company and the “Bank” shall mean the Bank, each as hereinbefore defined and any successor to its business and/or assets as aforesaid which assumes and agrees to perform this Agreement by operation of law, or otherwise.

12.Notices. For purposes of this Agreement, notices and all other communications provided for in this Agreement shall be in writing and shall be deemed to have been duly given (a) on the date of delivery, if delivered by hand, (b) on the date of transmission, if delivered by confirmed facsimile or electronic mail, (c) on the first business day following the date of deposit, if delivered by guaranteed overnight delivery service, or (d) on the fourth business day following the date delivered or mailed by United States registered or certified mail, return receipt requested, postage prepaid, addressed as follows:

or to such other address as either party may have furnished to the other in writing in accordance herewith, except that notices of change of address shall be effective only upon receipt.

13.Severability. To the extent that any provision of this Agreement is determined to be invalid or unenforceable, it shall be considered deleted herefrom and the remainder of such provision and of this Agreement shall be unaffected and shall continue in full force and effect.

14.Survival. The provisions of Sections 6, 9 and 10 hereof shall survive any termination of the Term or this Agreement.

15.Counterparts. This Agreement may be executed in several counterparts, each of which shall be deemed to be an original but all of which together shall constitute one and the same instrument.

16.Amendment; Waiver. No provision of this Agreement may be modified, waived or discharged unless such waiver, modification or discharge is agreed to in writing and signed by Consultant and the Company. No waiver by either party hereto at any time of any breach by the other party hereto of, or compliance with, any condition or provision of this Agreement to be performed by such other party shall be deemed a waiver of similar or dissimilar provisions or conditions at the same or at any prior or subsequent time.

17.Entire Agreement. Except as expressly provided herein, as of the Transition Date this Agreement represents the entire agreement and understanding between the parties hereto with respect to the subject matter hereof, supersedes any and all other agreements, verbal or otherwise, between the parties hereto concerning such subject matter, including, without limitation, the Employment Agreement, and no agreements or representations, oral or otherwise, express or implied, with respect to the subject matter hereof have been made by any party which are not expressly set forth in this Agreement.