Exhibit 23.1

- Consent of Independent Registered Public Accounting Firm -

The Board of Directors and Stockholders
First Community Bancshares, Inc.

We consent to the incorporation by reference in the registration statements pertaining to the 2004 Omnibus Stock Option Plan (Form S-8, No. 333-120376); the Commonwealth Bank Stock Option Plan (Form S-8, No. 333-106338); the 2001 Directors Stock Option Plan (Form S-8, No. 333-75222); the 1999 Stock Option Plan (Form S-8, 333-31338); the Employee Stock Ownership and Savings Plan (Form S-8, No. 333-63865); the Investments Planning Consultants Inc. acquisition (Form S-3, No. 333-142558); the Stone Capital Management acquisition (Form S-3, No. 333-104384); the Universal Shelf Registration (Form S-3, No. 333-153692); the Capital Purchase Program Warrant Resale (Form S-3, No. 333-156365); and the Greenpoint Insurance Group, Inc. acquisition (Form S-3, No. 333-148279) of First Community Bancshares, Inc. and Subsidiaries (the “Company”) of our report dated March 13, 2009, except for the effects of the restatement described in Note 2, for which the date is August 13, 2010, with respect to the consolidated financial statements of the Company and our report dated March 13, 2009, except for the effects of the material weakness described in Management’s Assessment of Internal Control over Financial Reporting, as to which the date is August 13, 2010 with respect to the effectiveness of internal control over financial reporting (which report expresses an adverse opinion on internal control over financial reporting), which reports appear in the Company’s 2008 Annual Report on Form 10-K/A.

Our audit report on the consolidated financial statements includes explanatory paragraphs relating to the restatement discussed in Note 2 to the consolidated financial statements and the adoption of the recognition and disclosure provisions of Statement of Financial Accounting Standards No. 157, Fair Value Measurements, Financial Accounting Standards Board Staff Position No. 157-3, Determining the Fair Value of a Financial Asset When the Market for That Asset Is Not Active, Emerging Issues Task Force 06-4, Accounting for Deferred Compensation and Postretirement Benefit Aspects of Endorsement Split-Dollar Life Insurance Arrangements, and Financial Accounting Standards Board Staff Position EITF Issue No 99-20-1, Amendments to the Impairment Guidance of EITF Issue No. 99-20.

Asheville, North Carolina
August 13, 2010