Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in the post-effective amendment No. 1 to the registration statements pertaining to the 2012 Omnibus Equity Compensation Plan (No. 333-183057); the 2004 Omnibus Stock Option Plan (No. 333-120376); the TriStone Community Bank Employee Stock Option Plan and the TriStone Community Bank Director Stock Option Plan (No. 333-161473); the Commonwealth Bank Amended and Restated Stock Option Plan (No. 333-106338); the 2001 Directors Stock Option Plan (No. 333-75222); the 1999 Stock Option Plan (No. 333-31338); and the Employee Stock Ownership and Savings Plan (No. 333-63865) on Form S-8 of First Community Bankshares, Inc. and Subsidiary (formerly named First Community Bancshares, Inc. and herein referred to as the “Company”) of our reports dated March 5, 2018, with respect to the consolidated financial statements of the Company and the effectiveness of internal control over financial reporting, which reports appear in the Company’s 2017 Annual Report on Form 10-K.

/s/ Dixon Hughes Goodman LLP

Asheville, North Carolina

October 2, 2018