Exhibit 10.1

FIRST amendment TO EMPLOYMENT AGREEMENT

THIS FIRST AMENDMENT TO EMPLOYMENT AGREEMENT (this “Agreement”) is made and entered into this 24^th day of May, 2016, by and between MARTYN A. PELL, a resident of North Carolina (“Executive”), and FIRST COMMUNITY BANCSHARES, INC., a Nevada Corporation, including subsidiaries and affiliates (the “Corporation” or “FCB”), both of whom together may be referred to herein as the “Parties.”

WITNESSETH:

WHEREAS, Executive is employed by FCB pursuant to an employment agreement dated January 1, 2015, (the “Employment Agreement”) and currently serves as President of FCB’s banking subsidiary, First Community Bank (hereinafter the “Bank”); and

WHEREAS, pursuant to Section 19 of the Employment Agreement, the Employment Agreement may be amended in writing by FCB and Executive; and

WHEREAS, FCB and Executive wish to amend the Employment Agreement, but only in and limited to the manner set forth in this Agreement.

NOW, THEREFORE, in consideration of the above premises, the mutual covenants of the parties hereto, and other good and valuable consideration, the receipt and sufficiency of which is hereby acknowledged, the Parties hereby agree the Employment Agreement shall be amended as follows:

1. Section 2 of the Employment Agreement shall be modified so that the Term shall expire at such time as Executive finds Alternative Employment, provided that such date shall not be later than January 1, 2017. For purposes of this Agreement, “Alternative Employment” is defined as any employment or engagement whatsoever for which Executive receives compensation of any kind, specifically including but not limited to the setting up of any business whether as a sole proprietor, in partnership with others, or through or for any corporation or business entity, and expressly including becoming a consultant or doing free-lance, part-time, or per-diem work. Executive agrees to not coordinate or delay Alternative Employment in order to foil or frustrate the intent of this provision or prolong his employment with FCB. Executive further agrees to immediately notify FCB in the event he obtains Alternative Employment, at which point his employment with the Bank will terminate, along with all employee benefits, executive benefits and perquisites. In addition, section 9 of the Employment Agreement is amended to allow Executive to provide fourteen (14) days prior written notice of resignation of his employment to the Corporation.

2. The Non-Compete Restriction set forth in Section 15 of the Employment Agreement shall remain in full force and effect for twenty four (24) months from the Date of Termination, and the definition of “Restricted Territory” in Section 15(a) of the Employment Agreement shall be revised to exclude all territories in North Carolina except the following counties: Allegheny, Alexander, Surry, Wilkes, Stokes, Yadkin and Catawba. Otherwise, the definition of “Restricted Territory” shall remain as set forth in Section 15(a) of the Employment Agreement, including the prohibitions against Executive not accepting employment with or provide services to or on behalf of any “Competing Financial Services Organization” which operates, or is seeking to open one or more branch facilities, within a fifty (50) mile radius of the Corporation’s headquarters or within a twenty-five (25) mile radius of any facility operated by the Corporation in West Virginia, Virginia, or Tennessee. Provided, however, Executive may be employed by a Competing Financial Services Organization in North Carolina so long as Executive is not personally present or personally providing services, directly or remotely, within the North Carolina counties of Allegheny, Alexander, Surry, Wilkes, Stokes, Yadkin and Catawba It is understood and agreed that the phrase “personally providing services, directly or remotely” does not include Executive performing company-wide responsibilities and services on behalf of a Competing Financial Services Organization.

3. The Anti-Piracy Restrictions set forth in Section 16 of the Employment Agreement shall be extended to Twenty-four (24) months from the Date of Termination and shall include all employees, including “Transferred Employees” as that term is defined in the P&A with First Bank.

4. The Non-Solicitation Restriction set forth in Section 14 of the Employment Agreement shall remain in full force and effect for twenty-four (24) months from the Date of Termination and shall specifically include, for a period of twenty-four (24) months, customers whose banking relationships were transferred to First Bank pursuant to the P&A.

5. Commencing with the date of this Agreement, Executive hereby agrees to continue to serve as Bank’s President through the Date of Termination, but without the current or customary duties associated with said office or the ability to bind the Bank or the Corporation in agreements with third parties. Further, upon execution of this Agreement, Executive will resign from the Board of Directors of the Bank, and will resign from other Boards and internal or external Committees associated with FCB and its affiliates when and as instructed by FCB, and Executive agrees to serve under the direction and in consultation with the Chief Executive Officer of the Bank.

6. Executive shall be entitled to no severance, continuing compensation, or other pay or benefits (other than as specifically and expressly set forth in this Agreement) subsequent to the Date of Termination.

7. Subject to the rights of Executive in paragraph 1 above, during the period from the date of this Agreement through July 31, 2016, Executive’s primary responsibility shall be to transition his duties to other staff of the Bank as determined by the CEO and to provide assistance with the Transactions and assist the closing of the Transactions and smooth transitions from and to the Bank, as appropriate, while also being available to the Bank on an as needed basis. The Parties acknowledge that during this time Executive will be seeking Alternative Employment. However, Executive is not obligated to stay employed with the Bank through July 31, 2016 in the event that Executive finds Alternative Employment or provides notice to the Bank of his resignation as provided in paragraph 1.

8. During the period from August 1, 2016, through January 1, 2017, the Executive will primarily focus on seeking Alternative Employment, but will continue to be available to the Bank on an as needed basis.

9. Executive shall be eligible to be considered for annual incentive compensation earned as a result of 2015 performance, as awarded by the Corporation’s Compensation and Retirement Committee (“CRC”), which is further subject to approval by the Corporation’s Board of Directors (“Board”), but without the need for an annual performance evaluation. Seventy-Five Percent (75%) of any such annual incentive compensation paid to Executive shall be paid in cash at the same time as is paid to other executives; the remaining Twenty-Five Percent (25%) will be paid in cash immediately upon the execution of this Agreement.

10. Executive is eligible to be considered for annual incentive compensation in 2017 based on 2016 performance, as awarded by the Corporation’s Compensation and Retirement Committee (“CRC”), but only if the Executive has not obtained Alternative Employment by the time that such incentive compensation, if any, is paid to other executives in 2017. This is at the sole discretion of the CRC and the Board of Directors. Under the Company’s existing annual incentive compensation methodology, the CRC’s decision whether to award any annual incentive compensation applies to the management team as a whole. If the CRC chooses to award such incentive compensation, any amount awarded to Executive shall only consider time and other factors relevant to the period beginning January 1, 2016 and ending July 31, 2016.

11. FCB will reimburse Executive for reasonable legal expenses of no more than Thirty-Five Hundred and 00/100 Dollars ($3,500.00) actually incurred by Executive for an independent review of this Agreement by counsel of Executive’s choice.

12. Executive shall execute a waiver and release of any and all claims against FCB. Such waiver and release, which shall be in substantially the same form as Exhibit A hereof, shall be executed twice: once upon entering into this Agreement and again as of the Date of Termination; however such waiver and release only becomes effective on the Date of Termination. It is understood and agreed that such waiver and release by Executive does not apply to any right of Executive or obligation of the Corporation or FCB contained in this Agreement.

13. This Agreement may be executed in one or more counterparts, which taken together shall constitute an original. This Agreement may not be modified in whole or in part except by a written document executed by both Parties.

14. Except as expressly modified or superseded by this Agreement, the Employment Agreement is hereby ratified and confirmed and all terms, conditions and obligations of the Employment Agreement and all other documents executed in connection therewith shall remain unaltered and in full force and effect as originally written therein, and each of said agreements are incorporated herein by reference. Whether or not specifically amended by this Agreement, all of the terms and provisions of the Employment Agreement are hereby amended to the extent necessary to give effect to the purpose and intent of this Agreement.

IN WITNESS WHEREOF, this First Amendment to Employment Agreement has been duly signed by an authorized officer of FCB and individually by Executive, respectively, all as of date first above written.