EXHIBIT 23.1

- Consent of Independent Registered Public Accounting Firm -

We consent to the incorporation by reference in the registration statements pertaining to the 2011 Series A Noncumulative Convertible Preferred Stock (Form S-3, No. 333-175262); the 2010 Universal Shelf Registration (Form S-3, No. 333-165965); 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 CommonWealth Bank acquisition (Form S-4, No. 333-104103); 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 Investment Planning Consultants Inc. acquisition (Form S-3, No. 333-142558); the Stone Capital Management acquisition (Form S-3, No. 333-104384); the 2008 Universal Shelf Registration (Form S-3, No. 333-153692); the Coddle Creek Financial Corporation acquisition (Form S-4, No. 333-153281); the Capital Purchase Program Warrant resale (Form S-3, No. 333-156365); the Greenpoint Insurance Group, Inc. acquisition (Form S-3, No. 333-148279); the TriStone Community Bank Employee and Director Stock Option Plans (Form S-8, No. 333-161473); and the 2012 Omnibus Equity Compensation Plan (Form S-8, No. 333-183057) of First Community Bancshares, Inc. and Subsidiaries (the “Company”) of our report dated August 22, 2012, with respect to the statement of assets acquired and liabilities assumed by First Community Bank (a wholly owned subsidiary of First Community Bancshares, Inc.), which report appears in this Amendment No. 2 of the Current Report on Form 8-K/A of First Community Bancshares, Inc. date August 22, 2012.

/s/ Dixon Hughes Goodman LLP

Charlotte, North Carolina

August 22, 2012