SCHEDULE 14A INFORMATION

PROXY STATEMENT PURSUANT TO SECTION 14(a) OF THE SECURITIES
EXCHANGE ACT OF 1934 (AMENDMENT NO. )

Filed by the Registrant /X/

Filed by a Party other than the Registrant / /

Check the appropriate box:

/X/ Preliminary Proxy Statement / / Confidential, for Use of the Commission
Only (as permitted by Rule 14a-6(e)(2))
/ / Definitive Proxy Statement
/ / Definitive Additional Materials
/ / Soliciting Material Pursuant to Rule 14a-11(c) or Rule 14a-12

FIRST COMMUNITY BANCSHARES, INC.
- --------------------------------------------------------------------------------
(Name of Registrant as Specified In Its Charter)

- --------------------------------------------------------------------------------
(Name of Person(s) Filing Proxy Statement, if other than the Registrant)

Payment of Filing Fee (Check the appropriate box):

/ / $125 per Exchange Act Rules 0-11(c)(1)(ii), 14a-6(i)(1), or 14a-6(i)(2) or
Item 22(a)(2) of Schedule 14A.

/ / $500 per each party to the controversy pursuant to Exchange Act Rule
14a-6(i)(3).

/ / Fee computed on table below per Exchange Act Rules 14a-6(i)(4) and 0-11.

(1) Title of each class of securities to which transaction applies:

(2) Aggregate number of securities to which transaction applies:

(3) Per unit price or other underlying value of transaction computed
pursuant to Exchange Act Rule 0-11 (Set forth the amount on which the
filing fee is calculated and state how it was determined):

(4) Proposed maximum aggregate value of transaction:

(5) Total fee paid:

/ / Fee paid previously with preliminary materials.

/ / Check box if any part of the fee is offset as provided by Exchange Act Rule
0-11(a)(2) and identify the filing for which the offsetting fee was paid
previously. Identify the previous filing by registration statement number,
or the Form or Schedule and the date of its filing.

(1) Amount Previously Paid:

(2) Form, Schedule or Registration Statement No.:

(3) Filing Party:

(4) Date Filed:

* No fee required
2

NOTICE OF ANNUAL MEETING AND PROXY STATEMENT

ANNUAL MEETING OF STOCKHOLDERS APRIL 11, 2000
3

ONE COMMUNITY PLACE
BLUEFIELD, VIRGINIA 24605-0989

NOTICE OF 2000
ANNUAL MEETING OF STOCKHOLDERS

To The Stockholders of First Community Bancshares, Inc.:

The ANNUAL MEETING of Stockholders of First Community Bancshares, Inc. will
be held at Fincastle Country Club, Double Gates, Bluefield,Virginia, at 3:00
p.m., local time on April 11, 2000, for the purpose of considering and voting
upon the following items as more fully discussed herein.

1. Election of four directors to serve as members of the Board of
Directors, Class of 2003.

2. To approve amendment of the Articles of Incorporation to increase
authorized common stock of the Company from ten million shares to
fifteen million shares.

3. Ratification of the selection of Ernst & Young, Charleston, West
Virginia, as independent auditors for the year ending December 31, 2000.

4. Transacting such other business as may properly come before the meeting,
or any adjournment thereof.

Only stockholders of record at the close of business on March 1, 2000 are
entitled to notice of and to vote at such meeting or at any adjournment thereof.

To ensure your shares are represented at the Annual Meeting, please
complete, sign and return the enclosed proxy as promptly as possible whether or
not you plan to attend the meeting. An addressed return envelope is enclosed for
your convenience. YOU MAY REVOKE YOUR PROXY AT ANY TIME PRIOR TO THE TIME IT IS
VOTED.

By Order of the Board of Directors

/s/ John M. Mendez

John M. Mendez, Secretary
4

PROXY STATEMENT

ANNUAL MEETING OF STOCKHOLDERS
TO BE HELD ON TUESDAY, APRIL 11, 2000

The Board of Directors of First Community Bancshares, Inc. (the
"Corporation") solicits the enclosed proxy for use at the Annual Meeting of
Stockholders of First Community Bancshares, Inc., which will be held on Tuesday,
April 11, 2000 at 3:00 p.m., (local time) at Fincastle Country Club, Double
Gates, Bluefield, Virginia, and at any adjournment thereof.

The expenses of the solicitation of the proxies for the meeting, including
the cost of preparing, assembling and mailing the notice, proxy statement and
return envelopes, the handling and tabulation of proxies received, and charges
of brokerage houses and other institutions, nominees or fiduciaries for
forwarding such documents to beneficial owners, will be paid by the Corporation.
In addition to the mailing of the proxy material, solicitation may be made in
person, by telephone or by other means by officers, directors or regular
employees of the Corporation.

This Proxy Statement and the proxies solicited hereby are being first sent
or delivered to stockholders of the Corporation on or about March 14, 2000.

VOTING

Shares of Common Stock (par value $1 per share) represented by proxies in
the accompanying form which are properly executed and returned to the
Corporation will be voted at the Annual Meeting in accordance with the
stockholder's instructions contained therein. In the absence of contrary
instructions, shares represented by such proxies will be voted FOR the election
of the nominees as described herein under "Election of Directors," FOR the
proposed amendment to the Articles of Incorporation, and FOR ratification of the
selection of Ernst & Young as independent public accountants for the year ended
December 31, 2000. Any stockholder has the power to revoke his proxy at any time
before it is voted.

The Board of Directors has fixed March 1, 2000 as the record date for
stockholders entitled to notice of and to vote at the Annual Meeting. Shares of
Common Stock outstanding on the record date are entitled to be voted at the
Annual Meeting and the holders of record will have one vote for each share so
held in the matters to be voted upon by the stockholders. There are no
cumulative voting rights.

Directors are elected by a plurality of votes present in person or by proxy
and entitled to vote, assuming a quorum is present. All other matters coming
before the meeting will be determined by majority vote of those present in
person or by proxy and entitled to vote. Abstentions and broker non-votes for
shares represented at the meeting thus have no direct effect on the election of
directors but have the effect of negative votes on other matters to be
considered.

As of the close of business on March 1, 2000, the outstanding shares of the
Corporation consisted of shares of Common Stock.

2
5

ELECTION OF DIRECTORS

The Corporation's Board of Directors is comprised of eleven directors,
including nine non-employee directors, divided into three classes with staggered
terms. All directors are elected for three-year terms.

The nominees for the Board of Directors to serve until the Annual Meeting
of Stockholders in 2003 are set forth below. All nominees are currently serving
on the Corporation's Board of Directors. In the event any nominee is unable or
declines to serve as a director at the time of the Annual Meeting, the proxies
will be voted for any nominee who shall be designated by the present Board of
Directors to fill the vacancy. In the event that additional persons are
nominated for election as directors, the proxy holders intend to vote all
proxies received by them for the nominees listed below. All nominees named
herein have consented to be named and to serve as directors if elected.

Principal Occupation and Director of Class
Employment Last Five Years; Corporation of
Name Age Principal Directorships Since Director
- --------------------------------------------------------------------------------------------------

James L. Harrison, Sr. 52 President & Chief Executive Officer of 1989 2003
the Corporation; President & Director,
First Community Bank, N.A.; Director,
United First Mortgage, Inc.

I. Norris Kantor 70 Of Counsel, Katz, Kantor & Perkins, 1989 2003
Attorneys-at-Law; Director, First
Community Bank, N.A.

A. A. Modena 71 Past Executive Vice President and 1989 2003
Secretary of the Corporation (Retired
October 1, 1994); Director, First
Community Bank, N.A.

William P. Stafford, II 36 Attorney, Brewster, Morhous & Cameron; 1994 2003
Director, First Community Bank, N.A.

3
6

CONTINUING DIRECTORS

The following persons will continue to serve as members of the Board of
Directors until the Annual Meeting of Stockholders in the year of the expiration
of their designated terms. The name, age principal occupation and certain
biographical information for each continuing director is presented below:

Sam Clark 68 Agent, State Farm Insurance; Director, 1993 2002
First Community Bank, N.A.

Allen T. Hamner 58 Professor of Chemistry, West Virginia 1993 2001
Wesleyan College; Director, First
Community Bank, N.A.

B. W. Harvey 68 President, Highlands Real Estate 1989 2001
Management, Inc.; Director, First
Community Bank, N.A.

John M. Mendez 45 Vice President, Chief Financial Officer 1994 2001
& Secretary of the Corporation;
Director, Senior Vice
President -- Finance & Chief
Administrative Officer, First Community
Bank, N.A.; Director, United First
Mortgage, Inc.

Robert E. Perkinson, Jr. 52 Past Vice President -- Operations, MAPCO 1994 2002
Coal, Inc.; Permac, Inc.; Race Fork Coal
Company; South Atlantic Coal, Inc.;
Director, Virginia Coal Association;
Administrative Officer, First Community
Bank, N.A.

William P. Stafford 66 President, Princeton Machinery Service, 1989 2002
Inc.; Chairman of the Board of the
Corporation; Director, First Community
Bank, N.A.

W. W. Tinder, Jr. 74 Chairman & Chief Executive Officer, 1989 2002
Tinder Enterprises, Inc.; President,
Tinco Leasing Corporation (Real Estate
Holdings); Director, First Community
Bank, N.A.

COMPENSATION OF DIRECTORS

During 1999, non-employee members of the Board of Directors received a
director's fee of $500 per month. Directors of the Corporation may also be
reimbursed for travel or other expenses incurred in attendance at Board or
committee meetings. Directors who are employees of the Corporation receive no
additional compensation for service on the Board or its committees.

MEETING ATTENDANCE

The Board of Directors held 12 meetings during 1999. All directors and
those nominees who are currently directors attended at least 75% of all meetings
of the Board and any committee of which they were a member.

4
7

BOARD COMMITTEES

The Board of Directors of the Corporation has an Audit Committee consisting
of Chairman Stafford and Messrs. Harvey and Tinder, all non-employee members of
the Board. The Audit Committee of the Board of Directors, which held 4 meetings
during 1999, reviews and acts on reports to the Board with respect to various
auditing and accounting matters, the scope of the audit procedures and the
results thereof, the internal accounting and control systems of the Corporation,
the nature of service performed for the Corporation by and the fees to be paid
to the independent auditors, the performance of the Corporation's independent
and internal auditors and the accounting practices of the Corporation. The Audit
Committee also recommends to the full Board of Directors the auditors to be
appointed by the Board (subject to stockholders' ratification).

The Board of Directors has a Compensation Committee which was formed in May
of 1999 consisting of non-employee Directors Hamner, Tinder, and William P.
Stafford, II. The Compensation Committee reviews and considers the form and
amount of compensation and contractual employment terms of the President and
Chief Executive Officer of the Corporation. Recommendations of the Compensation
Committee are made to the Board of Directors. The 1999 Report of the
Compensation Committee is presented on page 7 of this Proxy Statement

The Board of Directors of the Corporation has an Executive Committee
consisting of 7 members including the Chairman and Chief Executive Officer. The
Executive Committee held 7 meetings during 1999. The Executive Committee is
empowered to act on behalf of the Board on most Corporate matters not involving
business combinations.

The Board does not maintain a Nominating Committee.

TRANSACTIONS WITH DIRECTORS AND OFFICERS

Some of the directors and officers of the Corporation and members of their
immediate families are at present, as in the past, customers of the
Corporation's subsidiary bank, and have had and expect to have transactions with
the banks. In addition, some of the directors and officers of the Corporation
are, as in the past, also officers of or partners in entities which are
customers of the bank and which have had and expect to have transactions with
the bank. Such transactions were made in the ordinary course of business, were
made on substantially the same terms, including interest rates and collateral,
as those prevailing at the time for comparable transactions with other persons,
and did not involve more than normal risk of collectibility or present other
unfavorable features.

PRINCIPAL STOCKHOLDERS

The following sets forth information with respect to those persons who, to
the knowledge of management, beneficially owned more than 5% of the
Corporation's outstanding stock as of March 1, 2000. All shares are subject to
the named entity's sole voting and investment power.

Title of Shares Beneficially Percent
Class Name and Address of Beneficial Owner Owned of Class
- -----------------------------------------------------------------------------------------------

Common The H. P. & Anne S. Hunnicutt Foundation (1) 1,010,000 %
Common The First Community Bancshares, Inc. Employee %
Stock Ownership and Savings Plan

- ---------------
(1) William P. Stafford is deemed a beneficial owner of the same shares by
virtue of his position as President of the Foundation.

5
8

OWNERSHIP OF COMMON STOCK BY DIRECTORS AND EXECUTIVE OFFICERS

The following table sets forth the beneficial ownership of the Common Stock
of the Corporation as of March 1, 2000, by each director and nominee, each
executive officer named in the Summary Compensation Table, and all directors and
executive officers as a group including each executive officer named in this
Proxy Statement.

Percent of Class
Name of Group Number of Shares Beneficially Owned
- -----------------------------------------------------------------------------

Robert L. Buzzo *
Sam Clark *
Allen T. Hamner *
James L. Harrison, Sr. *
B. W. Harvey *
I. Norris Kantor *
John M. Mendez *
A. A. Modena *
Robert E. Perkinson, Jr. (1) *
William P. Stafford (2) %
William P. Stafford, II %
W. W. Tinder, Jr. *
All Directors and Executive Officers %
as a group (Twelve Persons)

- ---------------
(1) Mr. Perkinson serves as Co-trustee of the Trust Under Agreement for Robert
E. Perkinson, Sr., and by virtue of voting power is deemed to share
beneficial ownership of an additional shares or % of the
Corporation's outstanding stock held by the Trust.

(2) Mr. Stafford serves as President of The H. P. and Anne S. Foundation, and by
virtue of voting power is deemed to share beneficial ownership of an
additional 1,010,000 shares or % of the Corporation's outstanding stock
held by the Foundation.

* Less than one percent.

6
9

REPORT ON EXECUTIVE COMPENSATION

In 1999, the Board of Directors established the Compensation Committee (the
"Committee") whose role is the establishment and management of employment terms
and the form and levels of compensation paid to the President and Chief
Executive Officer ("CEO") and other senior executives of the Company. These
duties were previously assigned to the Executive Committee of the Board of
Directors. Compensation of other executive officers named in the Compensation
Table is managed by the CEO.

It is the responsibility of the Compensation Committee to develop proposed
contractual terms of employment and establish a framework for a competitive
compensation package for the CEO and other senior executives which adequately
rewards performance and provides incentives for retention. In carrying out its
responsibilities, the Compensation Committee considers: i) the need to retain
competent and effective management personnel; ii) competitive terms and levels
of compensation relative to other companies of comparable size and operation
within the commercial banking industry; iii) past performance of the incumbent
CEO as measured against predetermined goals and objectives; iv) comparative
performance of the incumbent CEO as benchmarked against peer groups of
comparable commercial banks; and v) the achievement of overall corporate goals
for growth in shareholder value.

In 1999, the Committee, along with the Executive Committee of the Board,
studied various strategies designed specifically to achieve the objective of
retention of key members of executive management. The Committee reviewed
proposals by three compensation consultants for the banking industry and
ultimately recommended to the Board of Directors the adoption of an Executive
Retention Plan and Stock Option Plan which the Committee believes will
significantly enhance the Company's ability to retain key executives through two
forms of long-term compensation with extended vesting schedules and forfeiture
of benefits in the event of voluntary termination prior to retirement. These
programs add the element of long-term, performance-based compensation and
supplemental retirement benefits for those executives who remain with the
Company through retirement. The programs were designed to attract long-term
performance but without limiting the Company's ability to effect management
changes, if and when deemed necessary. The Executive Retention Plan is designed
as a cost neutral plan to the Company. Likewise, the Stock Option Plan will
result in no stated compensation but may have the affect of nominal dilution of
earnings per share. The Executive Retention Plan and Stock Option Plan are
described in more detail on pages 9 through 11 of this Proxy Statement.

The Committee establishes current compensation based primarily on review of
competitive salary practices by similarly sized banking organizations locally
and nationally giving appropriate weight to regional differences in cost of
living and contrasting relative performance of the Company and the designated
peer group. In performing this analysis, the Committee utilized the SNL
Securities Executive Compensation Survey and data provided by Morehead
Consulting, as well as compensation data from other specifically identified
banking peers.

In 1999, the Committee reviewed the employment contract of the CEO and
determined that certain changes in contractual terms were advisable. Based on
that review and upon the Committee's recommendation to the Board of Directors, a
new employment contract ("contract") was adopted for the CEO. The new three-year
contract contains similar terms of employment and provides for salary
continuation for a period of 35 months in the event of termination within three
years of a change in control of ownership. The contract also provides for salary
continuation for a period of 30 months in the event of termination without
cause, absent a change in control of ownership.

Based on the Committee's evaluation of 1999 performance against budgetary
goals, it recommended to the Board of Director's a 3% annual bonus plus an
additional 3% bonus tied to

7
10

operating performance substantially beyond predetermined goals. As evidenced by
these short-term incentives, total compensation of the CEO is influenced by the
performance of the Company; however, the Committee does not assign weights to
the components of Company performance in establishing total compensation of the
CEO.

This report shall not be deemed to be incorporated by reference into any
filing under the Securities Act of 1933 or the Securities Exchange Act of 1934,
unless First Community Bancshares, Inc. specifically incorporates this report by
reference. It will not otherwise be filed under such Acts.

Allen T. Hamner
William P. Stafford, II
W. W. Tinder, Jr.

EXECUTIVE COMPENSATION FOR THE YEARS ENDED DECEMBER 31, 1999, 1998 AND 1997

The following summary compensation tables sets forth the information
concerning compensation for services in all capacities awarded to, earned by or
paid to the Corporation's President and Chief Executive Officer, and to other
executive officers of the Corporation whose salary and bonus exceeded $100,000
during the years ended December 31, 1999, 1998 and 1997.

SUMMARY COMPENSATION TABLE

Long-Term Compensation
----------------------
Awards
Securities Payouts
Name of Individual/ Underlying LTIP
Capacities in Which Other Annual Options Payouts
Served Year Salary Bonus Compensation (1) # $
- --------------------------------------------------------------------------------------------------------

James L. Harrison, Sr. 1999 $219,651 $ -- $29,965 16,129 $ --
President, Chief Executive 1998 $199,619 $ -- $46,609 -- $ --
Officer & Director of the 1997 $193,687 $ -- $56,274 -- $ --
Corporation; President & Director
of First Community Bank, N. A.;
Director of United First
Mortgage, Inc.
John M. Mendez 1999 $157,193 $ -- $ 6,156 11,660 $ --
Vice President, Chief 1998 $154,970 $14,969 $ 8,062 -- $ --
Financial Officer & 1997 $144,608 $22,910 $ 6,153 -- $ --
Secretary of the Corporation;
Senior Vice President -- Finance,
Chief Administrative Officer &
Director, First Community Bank,
N. A.; Director of United First
Mortgage, Inc.

8
11

Robert L. Buzzo 1999 $ 82,121 $ -- $ 7,416 6,253 $ --
Vice President of the 1998 $ 81,977 $ 3,154 $21,499 -- $ --
Corporation; Chief 1997 $ 80,402 $26,396 $13,943 -- $ --
Executive Officer of the
Bluefield Division of First
Community Bank, N. A

- ---------------
(1) Other annual compensation includes non-qualified deferred compensation
agreements, deferred bonuses and non-cash fringe benefits.

STOCK OPTIONS

In 1999, the Company instituted a Stock Option Plan to encourage and
facilitate investment in the common stock of the Company by key executives and
to assist in the long-term retention of service by those executives. The Plan
covers key executives as determined by the Company's Board of Directors from
time to time. Options under the Plan were granted in the form of non-statutory
stock options with the aggregate number of shares of common stock available for
grant under the Plan set at 275,000 shares. Total options granted under the Plan
during 1999 represent the rights to acquire 272,578 shares with deemed grant
dates of January 1 for each year 1999 through 2003 resulting in the deemed grant
of 54,516 shares in each year of the five-year deemed grant period. All stock
options granted pursuant to the Plan vest ratably on the first through the
seventh anniversary dates of the deemed grant date. The option price of each
stock option is equal to the fair market value of the Company's common stock on
the date of each deemed grant during the five-year grant period. Vested stock
options granted pursuant to the Plan are exercisable for a period of five years
after the date of the grantee's retirement (provided retirement occurs at or
after age 62), disability, or death. If employment is terminated other than by
retirement, disability, or death, vested options must be exercised within 90
days after the effective date of termination. Any option not exercised within
such period will be deemed cancelled.

In the event of a change of control or upon dissolution of the corporation,
the stock options granted under the Plan continue to vest and are exercisable in
accordance with the terms of the original grant. Change of control provisions
further provide that any optionee who is terminated without cause by the
corporation, its successor or affiliate during the 12 months preceding, or at
any time following a change of control, and any participant who remains employed
by the corporation or any affiliate during the 90-day period following a change
of control and thereafter resigns, shall continue to receive grants on the
deemed grant dates and vest as if the optionee continued to be employed and
optionee, or his estate, shall be entitled to exercise such options within five
years after death or attainment of age 62, whichever first occurs.

9
12

OPTION DEEMED GRANTED IN LAST FISCAL YEAR

Individual Grants
Number of % of Total Present Value of
Securities Options Grant at Date of
Underlying Granted to Exercise or Grant Using
Options Employees in Base Price Expiration Options
Name Granted (#) Fiscal Year ($/Sh) (1) Dates (2) Pricing Model
-------------------------------------------------------------------------------------------------

James L. Harrison, Sr. 16,129 29.6% 24.20 05/01/15 $71,290
John M. Mendez 11,660 21.4% 24.20 03/01/22 48,389
Robert L. Buzzo 6,253 11.5% 24.20 04/01/19 25,950
7 Optionees (Including 54,516 100.0% 24.20 From 2/01/08 243,687
the 3 Listed Above) To 8/01/25

- ---------------
(1) Plan participants may use previously owned shares to pay for an option's
exercise price. Additionally, plan participants may have the Company
withhold their shares due upon exercise of an option to satisfy their
required tax withholding obligations. The number of shares has been adjusted
for the 25% stock dividend declared on March 31, 1999.

(2) Options expire 5 years after the executive's retirement date, death or
disability. In the event of termination other than retirement, death or
disability, options must be exercised within 90 days of effective date of
termination. If not exercised within that period, options are deemed
cancelled. For purposes of this table, retirement age is assumed to be age
62.

(3) The present value of grant at date of grant values options using the
Black-Scholes model with the following assumptions: risk-free interest rate
of 6.25%, dividend yield of 4.5%, and volatility of the expected market
price of the Company's common stock of 32.8%.

(4) The number of shares under option has been adjusted for the 25% stock
dividend declared on March 31, 1999.

OPTION EXERCISES IN LAST FISCAL YEAR

The following table lists the number of shares underlying unexercised
options as well as values for "in-the-money" options. Options are "in-the-money"
if the 1999 year-end share price is higher than the exercise price. No options
were exercised for the listed officers in 1999, and no shares were acquired on
exercise.

OPTION EXERCISES IN LAST FISCAL YEAR

Value of
Number of Securities Unexercised
Underlying Unexercised In-the-Money
Options at FY-End Options at FY-End
Exercisable Exercisable
Name # $
- -----------------------------------------------------------------------------------------------------

James L. Harrison, Sr. 16,129 --
John M. Mendez 11,660 --
Robert L. Buzzo 6,253 --

EXECUTIVE RETENTION PLAN

In 1999, the Company established an Executive Retention Plan for key
members of senior management, including the individuals named in the Summary
Compensation Table. This Plan provides for a benefit at normal retirement (age
65) targeted at 15% of final compensation projected at

10
13

an assumed 3% salary progression rate. Benefits under the Plan became payable at
age 62. Actual benefits payable under the Retention Plan are dependant on an
indexed retirement benefit formula which accrues benefits equal to the aggregate
after-tax income of associated life insurance contracts less the Company's
tax-effected cost of funds for that plan year. Benefits under the Plan are
dependent on the performance of the insurance contracts and are not guaranteed
by the Company.

As of December 31, 1999, the Company had not acquired the associated life
insurance contracts. Accordingly, no benefits under the Plan have accrued. The
Company subsequently funded the contracts during the first quarter of 2000.

In connection with the Executive Retention Plan, the Company has also
entered into Life Insurance Endorsement Method Split Dollar Agreements (the
"Agreements") with the executives covered under the Retention Plan. Under the
Agreements, the Company shares 80% of death benefits (after recovery of cash
surrender value) with the designated beneficiaries of the executives under life
insurance contracts referenced in the Retention Plan. The Company as owner of
the policies retains a 20% interest in life proceeds and a 100% interest in the
cash surrender value of the policies.

The Retention Plan also contains provisions for change of control, as
defined, which allow the executives to retain benefits under the Plan in the
event of a termination of service, other than for cause during the twelve months
prior to a change in control or anytime thereafter, unless the executive
voluntarily terminates his employment within 90 days following the change in
control.

Because the Retention Plan was designed to retain the future services of
key executives, no benefits are payable under the Plan in the event of voluntary
or involuntary termination prior to retirement age of 62.

11
14

COMPARATIVE PERFORMANCE OF THE COMPANY

The following chart compares cumulative total shareholder return on the
Corporation's Common Stock for the five-year period ended December 31, 1999 with
cumulative total shareholder return of: (1) The Standard & Poor's 500 market
index ("S&P 500"); and (2) a group of five Peer Bank Holding Companies which was
selected by management of the Corporation based upon relative asset size and
geographic location.

FCBI S&P 500 PEER
---- ------- ----

'1994' 100.00 100.00 100.00
'1995' 112.00 137.00 116.00
'1996' 122.00 168.00 154.00
'1997' 181.00 220.00 222.00
'1998' 180.00 279.00 219.00
'1999' 147.00 333.00 206.00

The graph assumes an initial investment of $100 on December 31, 1994 in the
Corporation's common stock and each of the comparative investments with
dividends from each of the investments reinvested at year-end in additional
shares of the stock at the then current market value.

EMPLOYMENT CONTRACTS

Under the provisions of employment contracts with Messrs. Harrison and
Mendez, in the event of a change in control of the Corporation, Harrison and
Mendez may elect to terminate services and be compensated at their annual salary
for the balance of the term of the contract or for a period of thirty-five
months, whichever is greater. In the event either officer is dismissed for
reasons other than cause, as defined, he will be compensated at his annual
salary for the balance of the term of the three-year contract, thirty-five
months, whichever is greater.

EMPLOYEE STOCK OWNERSHIP PLAN

The individuals listed in the Summary Compensation Table are covered under
an Employee Stock Ownership and Savings Plan ("ESOP"). Contributions under the
ESOP feature are made annually at the discretion of the Board of Directors.
Allocations of those contributions to participants' accounts are made on the
basis of relative W-2 compensation (up to $160,000). Allocations to the accounts
of the individuals named in the Summary Compensation Table for the 1999 year
were: Harrison -- $16,000; Mendez -- $16,000; and Buzzo -- $8,955.

12
15

SAVINGS PLAN

The Plan also provides a 401(k) Savings feature and matches employee
contributions at the rate of 25% up to 6% of compensation. Matching
contributions for 1999 for the covered persons listed in the Summary
Compensation Table were as follows: Harrison -- $1,634; Mendez -- $1,663; and
Buzzo -- $906.

WRAP PLAN

The Corporation maintains a non-qualified Supplemental 401(k) Plan ("Plan")
for the purpose of providing deferred compensation which cannot be accumulated
under the Basic Plan provisions above because of deferral and covered
compensation limitations on tax-qualified pension plan benefits. The Company
makes a non-qualified matching credit on employee contributions at the rate of
25% up to 6% of compensation under the 401(k) feature of the basic plan and also
makes contributions in lieu of basic plan ESOP contributions for compensation in
excess of the $160,000 compensation limit. Contributions under this Plan in 1999
for the covered persons listed in the Summary Compensation Table were as
follows: Harrison -- $9,304; Mendez -- $2,484; and Buzzo -- $425.

INCREASE IN AUTHORIZED COMMON STOCK

Article Fourth of the Articles of Incorporation of the Company provides the
amount of total authorized capital stock of the Corporation shall consist of Ten
Million (10,000,000) shares of One dollar ($1.00) par value, common stock, and
One Million (1,000,000) shares of Twenty Dollar ($20.00) par value, preferred
stock. The Board recommends this Article Fourth be amended to increase such
authorized common stock from Ten Million (10,000,000) shares to Fifteen Million
(15,000,000) shares. This increase in authorized shares will provide additional
authority, if necessary, for the issuance of shares in the event of future
declarations of stock dividends and/or splits, if and when declared or for use
in potential business combinations. It is important to note future issuances of
stock in certain business combinations can be made only upon the affirmative
vote of shareholders as required by Sections 2 and 3 of Article Seventh of the
Articles of Incorporation. The Board of Directors unanimously recommends
approval of this proposal.

RATIFICATION OF THE SELECTION OF AUDITORS

Pursuant to the Bylaws of the Corporation, stockholders will be asked to
ratify the selection of Ernst & Young, Charleston, West Virginia, as independent
auditors of the Corporation and its subsidiaries for the fiscal year ended
December 31, 2000. The firm of Deloitte & Touche previously served as
independent auditors and examined the financial statements of the Corporation
and its subsidiaries each year since 1985. The Audit Committee of the Board of
Directors recommended to the Board of Directors a change in independent auditors
for 2000 based upon proposals received in January 2000. Ernst & Young was
selected as a qualified national firm based upon its qualifications, proposed
staffing, estimated fees and its proximity to the Company's operations from its
Charleston, West Virginia office. Ernst & Young has no relationship with the
Corporation or its subsidiaries except in its capacity as proposed Independent
Auditor. In connection with its audit of the Corporation's financial statements
for the year ended December 31, 2000, Ernst & Young will review the
Corporation's annual reports to stockholders and its filings with the Securities
and Exchange Commission and will conduct reviews of quarterly reports to
stockholders.

The Audit Committee of the Board of Directors has recommended to the Board
of Directors that Ernst & Young be appointed as independent auditors for the
year ended December 31, 2000. The Board

13
16

of Directors has made that appointment and recommends that the stockholders
ratify the selection of Ernst & Young as independent auditors for the ensuing
year.

A representative of Ernst & Young is not expected to be present at the
meeting. However, inquiries or questions of Ernst & Young may be directed to Mr.
Paul Arbogast, Partner, Ernst & Young, 900 United Center, Charleston, West
Virginia, 25301, (304) 343-8971.

OTHER MATTERS

All properly executed proxies received by the Corporation will be voted at
the meeting in accordance with the specifications contained thereon. The Board
of Directors knows of no other matter which may properly come before the meeting
for action. However, if any other matter does properly come before the meeting,
the persons named in the proxy materials enclosed will vote in accordance with
their judgment upon such matter.

STOCKHOLDERS PROPOSALS

If any stockholder intends to present a proposal at the 2001 Annual
Meeting, such proposals must be received by the Corporation at its principal
executive offices on or before November 18, 2000. Otherwise, such proposal will
not be considered for inclusion in the Corporation's Proxy Statement for such
meeting.

You are urged to properly complete, execute and return the enclosed form of
proxy.

By Order of the Board of Directors

/s/ John M. Mendez

John M. Mendez, Secretary to the Board
March 14, 2000

14
17

PROXY FOR ANNUAL MEETING OF STOCKHOLDERS
FIRST COMMUNITY BANCSHARES, INC. o ONE COMMUNITY PLACE,
BLUEFIELD, VA 24605
THIS PROXY IS SOLICITED ON BEHALF OF THE BOARD OF DIRECTORS

The undersigned hereby constitutes and appoints Robert L. Schumacher and Barbara
J. Buchanan, or either of them, attorney and proxy with full power of
substitution, to present the undersigned at the Annual Meeting of the
Stockholders of First Community Bancshares, Inc. (the "Corporation") to be held
on Tuesday, April 11, 2000, at the Fincastle Country Club, Double Gates,
Bluefield, Virginia, at 3:00 P.M., local time, and any adjournments thereof,
with all power then possessed by the undersigned, and to vote, at that meeting
or any adjournment thereof, all shares which the undersigned would be entitled
to vote if personally present.

1. FOR [ ] the election of 4 directors - Class of 2003 WITHHOLD AUTHORITY [ ]
James L. Harrison, Sr. A. A. Modena You may withhold authority to vote for any
I. Norris Kantor William P. Stafford, II nominee by lining through or otherwise
striking out his name.

2. To approve amendment of the Articles of Incorporation to increase
authorized common stock of the Company from ten million shares to fifteen
million shares.

FOR [ ] AGAINST [ ] ABSTAIN [ ]

3. To ratify the selection of the firm of Ernst & Young, Charleston, West
Virginia, as independent auditors for the year ending December 31, 2000.

FOR [ ] AGAINST [ ] ABSTAIN [ ]

4. To vote upon such other business as may properly come before this meeting.

CONTINUED ON THE REVERSE

SHARES REPRESENTED BY THIS PROXY WILL BE VOTED AS SPECIFIED, IF AUTHORITY IS
NOT WITHHELD OR IF NO CHOICE IS SPECIFIED, THIS PROXY WILL BE VOTED FOR ITEMS 1,
2 AND 3 ABOVE.

Dated: _______________________, 2000 ________________________________
Signature of Stockholder

________________________________
Signature of Stockholder

[ ] PLEASE CHECK IF YOU PLAN TO
ATTEND THE STOCKHOLDERS'
MEETING ON APRIL 11, 2000

Please sign your name(s) exactly
as shown imprinted hereon. If
more than one name appears as
part of registration name, all
names must sign. If acting in
executor, trustee or other
fiduciary capacity, please sign
as such.