Check the appropriate box below if the Form 8-K filing is intended to simultaneously satisfy the filing obligation of the registrant under any of the following provisions:

Explanatory Note

On August 13, 2013, First Community Bancshares, Inc. (the “Company”) filed a current report on Form 8-K (the “Original 8-K”) to report information relating to the departure of John M. Mendez, the Chief Executive Officer and a Director of the Company, the appointments of William P. Stafford II, Chairman of the Board of Directors to serve as interim Chief Executive Officer of the Company, Gary R. Mills to serve as to serve as Chief Executive Officer of the Company’s subsidiary, First Community Bank (the “Bank”) and Martyn A. Pell to serve as President of the Bank, all effective August 31, 2013. The Company hereby amends the Original 8-K to disclose: (i) information relating to Mr. Mendez’s execution of a separation and release agreement with the Company, and (ii) the appointment of Robert L. Buzzo to serve as President Emeritus of the Bank. This 8-K/A should be read in conjunction with the Original 8-K.

(b) (c) On August 28, 2013, the Company and John M. Mendez, President, Chief Executive Officer, and Director of the Company entered into a Separation Agreement and Release (the “Separation and Release Agreement”) which confirms and clarifies certain benefits and restrictions set forth in the Employment Agreement entered into by the Company and Mr. Mendez on December 16, 2008, as amended December 16, 2010 (the “Employment Agreement”). As provided in the Employment Agreement, upon a termination not for cause, Mr. Mendez will receive his current base salary in effect on the Termination Date for a period of thirty (30) months, specified health and dental benefits and a monthly car allowance of $800, subject to any applicable six month delay under Internal Revenue Code Section 409A. Under the terms and conditions of certain qualified and non-qualified retirement plans, Mr. Mendez is also entitled to receive retirement benefits under the Company’s qualified retirement plan, non-qualified 401(k) WRAP Plan, and non-qualified Executive Retention Plan. Mr. Mendez was previously granted options to purchase 42,323 shares of common stock of the Company, ownership of certain life insurance policies, and 3,731 shares of common stock of the Company, all of which he will retain at termination, subject in the case of the options, to the terms and conditions of the applicable Option Agreement and Plan. In addition, the Company agreed to reimburse Mr. Mendez for any fees and expenses reasonably incurred by him in connection with the Executive’s negotiation, execution and delivery of the Separation Agreement and Release up to a maximum amount of $15,000. As further consideration for the release, the Company will pay Mr. Mendez $15,000. Mr. Mendez also resigned as a director of the Company and its subsidiaries effective August 31, 2013. Pursuant to the terms of the Separation and Release Agreement, Mr. Mendez is also subject to certain restrictive covenants, including restrictions for thirty-six months on his ability to compete with the Company, its subsidiaries and affiliates, and his ability to solicit the employees, customers or other business relationships thereof. Mr. Mendez is also prohibited from disclosing confidential information or disparaging the Company, its subsidiaries, affiliates, directors, officers, employees or stockholders. In accordance with applicable law, Mr. Mendez may revoke the Separation and Release Agreement for a period of seven days after the date on which it was executed, and the Separation and Release Agreement will not become effective or enforceable until after the expiration of such seven-day revocation period.

A copy of the Separation and Release Agreement by and between the Company, the Bank, and Mr. Mendez is attached as Exhibit 99.1.

Additionally, the Board of Directors of the Company appointed Robert L. Buzzo to serve as President Emeritus of the Bank effective August 31, 2013. Mr. Buzzo, age 63, previously served as President of the Bank since 2000. Mr. Buzzo will continue service to the Company and the Bank in all areas and with all responsibility previously held. There are no arrangements or understandings between Mr. Buzzo and any other person or persons pursuant to which Mr. Buzzo was appointed President Emeritus.

SIGNATURES

Pursuant to the requirements of the Securities Exchange Act of 1934, the registrant has duly caused this report to be signed on its behalf by the undersigned hereunto duly authorized.