SCHEDULE 14A INFORMATION

Proxy Statement Pursuant to Section 14(a) of the Securities Exchange Act of 1934

                           Filed by the Registrant [X]
                 Filed by a Party other than the Registrant [ ]

                           Check the appropriate box:

                         [ ] Preliminary Proxy Statement
        [ ] Confidential, for Use of the Commission Only (as permitted by
                                Rule 14a-6(e)(2))
                         [X] Definitive Proxy Statement
                       [ ] Definitive Additional Materials
 [ ] Soliciting Material Pursuant to Section 240.14a-11(c) or Section 240.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):

[X] No fee required.
[ ] $125 per Exchange Act Rule O-11(c)(1)(ii), 14a-6(i)(l), 14a-6(i)(2) or
    Item 22(a)(2) of Schedule 14A.
[ ] Fee computed on table below per Exchange Act Rules 14a-6(i)(4) and O-11.

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

--------------------------------------------------------------------------------
2) Aggregate number of securities to which transaction applies:
Not applicable

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

--------------------------------------------------------------------------------
4) Proposed maximum aggregate value of transaction:
Not applicable

--------------------------------------------------------------------------------
5) Total fee paid:
Not applicable
--------------------------------------------------------------------------------

[ ] Fee paid previously by written preliminary materials.
[ ] Check box if any part of the fee is offset as provided by Exchange Act Rule
O-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: Not applicable
2) Form Schedule or Registration Statement No.: Not applicable
3) Filing Party: Not applicable
4) Date Filed: Not applicable






                        FIRST COMMUNITY BANCSHARES, INC.
                              ONE COMMUNITY PLACE
                         BLUEFIELD, VIRGINIA 24605-0989

                                 NOTICE OF 2004
                         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, Bluefield, Virginia, at 3:00 p.m. local time
on Tuesday April 27, 2004, for the purpose of considering and voting upon the
following items as more fully discussed herein.

     1. The election of directors to serve as members of the Board of Directors,
Class of 2007.

     2. The ratification of the 2004 Omnibus Stock Option Plan

     3. The ratification of the selection of Ernst & Young LLP, as independent
        auditors for the year ending December 31, 2004; and

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 9, 2004 are entitled to notice of and to vote at such meeting or at any
adjournment thereof.

                                          By Order of the Board of Directors

                                          /s/ Robert L. Buzzo
                                          Robert L. Buzzo, Secretary

                                   IMPORTANT

YOU MAY VOTE BY THE FOLLOWING METHODS:

1. By telephone: (888) 216-1279; or

2. on the internet at www.proxyvotenow.com/fcb until 11:59 p.m. eastern daylight
   time on April 26, 2004; or

3. 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.


                                PROXY STATEMENT

                         ANNUAL MEETING OF STOCKHOLDERS
                     TO BE HELD ON TUESDAY, APRIL 27, 2004

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

     The expenses of the solicitation of the proxies for the Annual 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 20, 2004.

VOTING

     Shares of common stock (par value $1 per share) ("Common Stock")
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 2004 Omnibus Stock Option Plan and FOR ratification of the selection of
Ernst & Young LLP as independent public auditors for the year ended December 31,
2004.

     Any stockholder has the power to revoke his proxy at any time before it is
voted. A proxy may be revoked at any time prior to its exercise by the filing of
written notice of revocation with the secretary of the Corporation, by
delivering to the Corporation a duly executed proxy bearing a later date, or by
attending the Annual Meeting and voting in person. However, if you are a
stockholder whose shares are not registered in your own name, you will need
additional documentation from your recordholder to vote personally at the Annual
Meeting.

     The Board of Directors has fixed March 9, 2004 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. Shareholders of the
Corporation do not have cumulative voting rights.

     The presence in person or by proxy of a majority of the shares of the
Common Stock entitled to vote is necessary to constitute a quorum at the Annual
Meeting. Directors are elected by a plurality of the votes cast with a quorum
present. The three persons who receive the greatest number of votes of the
holders of Common Stock represented in person or by proxy at the Annual Meeting
will be elected directors of the Corporation. The proposal to ratify the 2004
Omnibus Stock Option Plan requires that the number of votes cast in favor of the
proposal exceed the number of votes cast against it. The proposal to ratify the
appointment of the independent auditors requires that the number of votes cast
in favor of the proposal exceed the number of votes cast against it. Abstentions
are considered in determining the presence of a quorum but will not affect the
vote required for the election of directors or the ratification of the
independent auditors. All of the proposals for consideration at the Annual
Meeting are considered "discretionary" items upon which brokerage firms may vote
in their discretion on behalf of their clients if such clients have not
furnished voting instructions; however, under New York Stock Exchange Rule 452
which applies to members of a national securities exchange broker non-votes with
respect to an equity compensation plan, such as the 2004 Omnibus Stock Plan, are
prohibited. Therefore, brokers will not be able to vote for any stockholders on
the proposal to adopt our 2004 Omnibus Stock Plan in the absence of specific
instructions from the beneficial owner.

     As of the close of business on March 9, 2004, the outstanding shares of the
Corporation consisted of 11,242,396 shares of Common Stock.

                                        1


                           1.  ELECTION OF DIRECTORS

     The Corporation's Board of Directors is comprised of nine directors,
including eight non-employee directors, divided into three classes with
staggered terms. All directors are elected for three-year terms. All directors
have been determined to be independent by the Board of Directors except for Mr.
William P. Stafford who is deemed not independent due to his affiliation with
and his services as Chairman of the H. P. & Anne S. Hunnicutt Foundation, a
holder of more than 10% of the outstanding shares of the Corporation, and Mr.
John M. Mendez, who is employed by the Corporation as President and Chief
Executive Officer.

     The nominees for the Board of Directors to serve until the Annual Meeting
of Stockholders in 2007 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.

     No director or executive officer of the Corporation is related to any other
director or executive officer of the Corporation by blood, or marriage or
adoption, except for Mr. Stafford who is the father of Mr. Stafford, II.



                                           PRINCIPAL OCCUPATION AND             DIRECTOR OF     CLASS
                                         EMPLOYMENT LAST FIVE YEARS;            CORPORATION      OF
NAME                       AGE             PRINCIPAL DIRECTORSHIPS                 SINCE      DIRECTORS
----                       ---           ---------------------------            -----------   ---------
                                                                                  
Allen T. Hamner            62    Professor of Chemistry, West Virginia             1993         2007
                                 Wesleyan College; Director, First Community
                                 Bank, N. A.; Member of Audit, Executive and
                                 Compensation Committees

B. W. Harvey               72    President, Highlands Real Estate Management,      1989         2007
                                 Inc. (a Corporation which provides
                                 commercial property leasing services);
                                 Director and Chairman First Community Bank,
                                 N. A.; Financial Expert on Audit Committee,
                                 Member of Executive, Bank Loan and Trust
                                 Committees

John M. Mendez             49    President and Chief Executive Officer of the      1994         2007
                                 Corporation; Director, Executive Vice
                                 President, First Community Bank, N. A.; Past
                                 Vice President, Chief Financial Officer &
                                 Secretary of the Corporation; Past Senior
                                 Vice President -- Finance & Chief
                                 Administrative Officer, First Community
                                 Bank, N. A.


     THE BOARD OF DIRECTORS RECOMMENDS A VOTE "FOR" EACH OF THE NOMINEES FOR
DIRECTOR.

                                        2


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 are presented below:



                                           PRINCIPAL OCCUPATION AND             DIRECTOR OF     CLASS
                                         EMPLOYMENT LAST FIVE YEARS;            CORPORATION      OF
NAME                       AGE             PRINCIPAL DIRECTORSHIPS                 SINCE      DIRECTORS
----                       ---           ---------------------------            -----------   ---------
                                                                                  
Robert E. Perkinson, Jr.   56    Mayor of City of Bluefield, WV; Past Vice         1994         2005
                                 President-Operations, MAPCO Coal, Inc.,
                                 Permac, Inc., Race Fork Coal Company, South
                                 Atlantic Coal, Inc., (all coal mining
                                 operations); Director, First Community Bank,
                                 N. A.; Chairman of Audit Committee and
                                 Member of Bank Loan Committee

William P. Stafford        70    President, Princeton Machinery Service, Inc.      1989         2005
                                 (a machinery manufacturing and repair
                                 company); Chairman of the H. P. & Anne S.
                                 Hunnicutt Foundation; Chairman of the Board
                                 of the Corporation; Director, First
                                 Community Bank, N. A.; Member of Executive
                                 and Bank Loan Committees

Harold V. Groome, Jr.      59    Chairman, Groome Transportation, Inc.;            2003         2005
                                 Chairman, Groome Transportation of Georgia,
                                 Inc.;( a provider of personal and business
                                 transportation services); Director, First
                                 Community Bank, N. A.

I. Norris Kantor           74    Of Counsel, Katz, Kantor & Perkins                1989         2006
                                 Attorneys-at-Law; Director of Mercer Realty,
                                 Inc., a Real Estate Management Company;
                                 Director, First Community Bank, N. A.;
                                 Member of Bank Loan and Trust Committees

A. A. Modena               75    Trustee of United Company Investement Fund        1989         2006
                                 (a Mutual Fund), Bristol, VA; Trustee of
                                 Bluefield College, Bluefield, VA; Retired
                                 Executive Vice President and Secretary of
                                 the Corporation; Director, First Community
                                 Bank, N. A.; Member of Executive, Nominating
                                 and Compensation Committees and Chairman of
                                 Bank Trust Committee

William P. Stafford, II    40    Attorney, Brewster, Morhous, Cameron,             1994         2006
                                 Mullins, Caruth, Moore, Kersey & Stafford,
                                 PLLC; Director, First Community Bank, N. A.;
                                 Member of Executive, Compensation and Bank
                                 Trust Committees


                                        3


EXECUTIVE OFFICERS WHO ARE NOT DIRECTORS

     The name, age, principal occupation and certain biographical information
for each continuing officer are presented below:



                                                 PRINCIPAL OCCUPATION AND                 DIRECTOR OF
                                                EMPLOYMENT LAST FIVE YEARS;               CORPORATION
NAME                          AGE                 PRINCIPAL DIRECTORSHIPS                    SINCE
----                          ---               ---------------------------               -----------
                                                                                 
Robert L. Buzzo               53     President of First Community Bank, N. A.; Vice          2000
                                     President and Secretary of the Corporation; past
                                     Chief Executive Officer of First Community
                                     Bank -- Bluefield, a division of First Community
                                     Bank, N. A.

E. Stephen Lilly              45     Chief Operating Officer of the Corporation;             2000
                                     Senior Vice President and Chief Operating Officer
                                     of First Community Bank, N. A.; past Vice
                                     President-Operations of First Community Bank, N.
                                     A.

Robert L. Schumacher          52     Chief Financial Officer of the Corporation;             2000
                                     Senior Vice President-Finance and Secretary of
                                     First Community Bank, N. A.; Past Senior Vice
                                     President-Finance of the Corporation; Past Senior
                                     Vice President and Senior Trust Officer of First
                                     Community Bank, N. A.


COMPENSATION OF DIRECTORS

     During 2003, non-employee members of the Board of Directors received a
retainer fee of $700 per month. During 2003, Audit Committee members received a
retainer fee of $1,000 per quarter. Members of the Corporation's Executive
Committee also receive a fee of $250 per meeting unless held in conjunction with
monthly board meetings in which case no committee fee is paid. Directors of the
Corporation may also be reimbursed for travel or other expenses incurred for
attendance at Board or committee meetings. Directors who are employees of the
Corporation receive no compensation for service on the Board or its committees.

     In addition, non-employee directors of the Corporation participate in the
2001 Directors' Stock Option Plan (the "Directors' Option Plan"). The Directors'
Option Plan was implemented to facilitate and encourage investment in the
Corporation's future growth and continued success. No grants were made under the
Director's Option Plan in fiscal 2003. In fiscal 2001, non-employee directors
were granted options to purchase 45,000 shares of Common Stock. Considering 10%
stock dividends distributed in both 2002 and 2003, as well as certain option
exercises, the outstanding options exercisable at December 31, 2003 by
non-employee directors were 35,140 shares. The exercise price of each option was
the market value of a share of Common Stock on the date of grant adjusted for
the aforementioned stock dividends. The options are fully vested and must be
exercised within 10 years of grant or two years following the director's
retirement, whichever occurs first.

MEETING ATTENDANCE

     The Board of Directors held thirteen meetings during 2003. 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 members. Directors
are encouraged to attend annual meetings of the Corporation's stockholders. All
of the members of the Board of Directors attended last year's Annual Meeting.

BOARD COMMITTEES

  AUDIT COMMITTEE

     The Board of Directors of the Corporation has an Audit Committee consisting
of Chairman Perkinson and Messrs. Hamner and Harvey, all non-employee members of
the Board. Each Audit Committee member is independent under the Nasdaq Stock
Market listing standards as well as the Sarbanes-Oxley Act of 2002.

                                        4


Mr. Stafford served on the Audit Committee during 2002 and through the early
part of March, 2003. The Audit Committee of the Board of Directors, which
operates under a Board approved charter, held ten meetings during 2003, 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. In December of 2003, the Board
of Directors designated Mr. Harvey as the Audit Committee's Financial Expert,
based upon his qualifications and experience. The Audit Committee is responsible
for the appointment of the independent auditors, subject to stockholders'
ratification. The 2003 Report of the Audit Committee is presented on page 9 of
this Proxy Statement.

  COMPENSATION COMMITTEE

     The Board of Directors has a Compensation Committee that was formed in May
1999 consisting of non-employee Directors Hamner, Modena, and William P.
Stafford, II. The Compensation Committee, which held three meetings in 2003,
reviews and considers the form and amount of compensation and contractual
employment terms of the President and Chief Executive Officer of the
Corporation; reviews the compensation of other executive officers and reviews
stock-based compensation plans and various non-qualified compensation and
retirement programs maintained by the Corporation. Recommendations of the
Compensation Committee are made to the Board of Directors. The 2003 Report of
the Compensation Committee is presented on page 8 of this Proxy Statement.

  EXECUTIVE COMMITTEE

     The Board of Directors of the Corporation has an Executive Committee
consisting of Chairman Stafford and Messrs. Hamner, Harvey, Mendez, Modena, and
Stafford, II. The Executive Committee held two meetings during 2003. The
Executive Committee is empowered to act on behalf of the Board on most corporate
matters not involving business combinations.

  NOMINATING COMMITTEE

     The Board of Directors established a Nominating Committee in 2003. The
Nominating Committee assumed certain responsibilities formerly delegated to the
Executive Committee. The Nominating Committee is comprised of Directors Harvey,
Hamner and Modena, all independent directors. The committee operates under a
Board approved charter which outlines responsibilities including the review of
the composition and qualifications of the Board of Directors, periodic
evaluation of the Board and its effectiveness, review of Board membership needs,
search, screening and evaluation of director nominees and the evaluation of and
response to shareholder proposals regarding board composition and membership
when and if presented to the Corporation. A copy of the Nominating Committee
Charter is set forth as Annex A hereto.

     Nominations to the Board of Directors by stockholders to be considered at
the 2005 annual meeting of stockholders shall be made in writing and shall be
delivered or mailed to the Corporate Secretary not less than thirty days prior
to the 2005 annual meeting. However, in the event that less than thirty days
notice of the 2005 annual meeting is given to stockholders, such notice of
nomination shall be mailed or delivered to the Corporate Secretary no later than
the close of business on the seventh day following the day on which the notice
of the meeting was mailed. The notice must set forth the candidate's name, age,
business address, residence address, principal occupation or employment, the
number of shares beneficially owned by the candidate, qualifications for Board
membership and information that would be required to solicit a proxy under
federal securities law. In addition, the notice must include the nominating
shareholder's name, address, and the number of shares beneficially owned (and
the period they have been held).

                                        5


     The Nominating Committee will consider shareholder recommendations for
board candidates when the recommendations are properly submitted. Any
shareholder recommendations for candidates to be nominated for board service,
which are submitted under the criteria summarized above should be addressed to:

         Corporate Secretary
         First Community Bancshares, Inc.
         P.O. Box 989
         Bluefield, Virginia 24605-0989

     In evaluating and determining whether to recommend a candidate for
nomination to a position on the Corporation's Board, the Nominating Committee
will consider criteria as established by the Nominating Committee and used to
determine a candidate's suitability for board service, which criteria include at
a minimum, high professional ethics and values, relevant experience and a
commitment to enhancing shareholder value. In evaluating candidates for
nomination, the Nominating Committee utilizes a variety of methods. The
Corporation regularly assesses the size of the Board, whether any vacancies are
expected due to retirement or otherwise, and the need for particular expertise
on the Board. Candidates may come to the attention of the Nominating Committee
from current Board members, shareholders, professional search firms, officers or
other persons. The Nominating Committee will review all candidates in the same
manner regardless of the source of the recommendation.

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 bank. In addition, some of the directors and officers of the Corporation
are, as in the past, also officers of or partners in entities that are customers
of the bank and 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.

     One of the directors, Mr. Stafford, II, is a practicing attorney with
Brewster, Morhous, Cameron, Mullins, Caruth, Moore, Kersey & Stafford, PLLC, a
Bluefield, West Virginia law firm which provides general legal services to the
Corporation. The Corporation paid that firm $57,948 for these professional
services in 2003.

     The Corporation is currently in the process of building a bank facility in
Princeton, WV at an estimated cost of $1.8 million and the general contractor
for this project is Fredeking Stafford Construction Company, Inc. The majority
owner of Fredeking Stafford Construction Company, Inc. is the son of Mr.
Stafford and the brother of Mr. Stafford, II. Fredeking Stafford Construction
Company, Inc. provided other general contracting services to the Corporation
during 2003, for which the Corporation paid $62,414. Contracts for the largest
of these services were awarded through a competitive bidding process.

SECTION 16(a) BENEFICIAL OWNERSHIP REPORTING COMPLIANCE

     Section 16(a) of the Securities and Exchange Act of 1934 (the "Exchange
Act") requires the Corporation's officers, directors and persons who own more
than 10% of the Corporation's capital stock (collectively, "Reporting Persons")
to file reports of ownership and changes in ownership with the Securities and
Exchange Commission and the National Association of Securities Dealers, Inc. The
Reporting Persons are required by regulation to furnish the Corporation with
copies of all forms they file pursuant to Section 16(a) of the Exchange Act.

     Based solely on review of the copies of such forms furnished to the
Corporation, or written representations from its officers and directors, the
Corporation believes that during, and with respect to, fiscal 2003, the
Corporation's officers and directors complied in all respects with the reporting
requirements promulgated under Section 16(a) of the Exchange Act except for Mr.
Harold V. Groome, Jr. who filed a late Form 3 in connection with his appointment
to the Board in June of 2003.

                                        6


BENEFICIAL OWNERSHIP OF COMMON STOCK BY CERTAIN BENEFICIAL OWNERS AND MANAGEMENT

     The following table sets forth as of March 9, 2004, certain information as
to the Common Stock beneficially owned by (i) each person or entity, including
any "group" as that term is used in Section 13(d)(3) of the Exchange Act, who or
which was known to the Corporation to be the beneficial owner of more than 5% of
the issued and outstanding Common Stock, (ii) certain directors and executive
officers of the Corporation and its major subsidiaries and (iii) all directors
and executive officers of the Corporation and its major subsidiaries, as a
group. Except as otherwise indicated, the persons named in the table below have
sole voting and investment power with respect to the Common Stock shown as
beneficially owned by them.



                                                        AMOUNT AND NATURE
NAME AND ADDRESS OF BENEFICIAL                            OF BENEFICIAL
OWNER OR NUMBER OF                                       OWNERSHIP AS OF     PERCENT OF
PERSONS IN GROUP                                          MARCH 9, 2004     COMMON STOCK
------------------------------                          -----------------   ------------
                                                                      
The H. P. & Anne S. Hunnicutt Foundation (1)..........      1,222,100          10.77%
P.O. Box 309, Princeton, WV 24740

The Company's Directors and Officers:
Robert L. Buzzo(2)....................................         13,954              *
Harold V. Groome, Jr.(12).............................         29,451              *
Allen T. Hamner(3) (4)................................         14,499              *
B. W. Harvey(3) (5)...................................         18,673              *
I. Norris Kantor(13)(6)...............................         32,863              *
E. Stephen Lilly(7)...................................          6,539              *
John M. Mendez(8).....................................         18,799              *
A. A. Modena(3).......................................         33,674              *
Robert E. Perkinson, Jr.(3) (9).......................         83,486              *
Robert L. Schumacher(10)..............................         12,815              *
William P. Stafford(11)...............................        239,014           2.12%
William P. Stafford, II...............................        153,775           1.37%
All Directors and Executive Officers
  as a Group (Twelve Persons).........................        657,542           5.80%


 *  Represents less than 1% of the outstanding shares.

 (1) Information obtained from a Schedule 13G dated March 17, 2003. The H. P.
     and Anne S. Hunnicutt Foundation ("Foundation") is a private, tax-exempt
     charitable foundation under Section 501(c)(3) of the Internal Revenue Code.
     The Foundation was created by the family of two directors, William P.
     Stafford and William P. Stafford, II. Neither director exercises voting or
     dispositive power over the shares held by the Foundation.

 (2) Includes 13,682 shares allocated to Mr. Buzzo's Employee Stock Ownership
     and Savings Plan ("ESOP") account.

 (3) Includes 6,050 shares issuable upon exercise of currently exercisable
     options granted under the Directors' Option Plan.

 (4) Includes 4,712 shares held by Mr. Hamner's wife.

 (5) Includes 1,449 shares held by Mr. Harvey's wife.

 (6) Includes 1,403 shares held by Mr. Kantor's wife.

 (7) Includes 3,011 shares allocated to Mr. Lilly's ESOP account.

 (8) Includes 17,423 shares allocated to Mr. Mendez's ESOP account.

                                        7


 (9) Includes 21,863 shares held by the Robert E. Perkinson, Sr. Trust, 5,138
     shares held by the Robert E. Perkinson, Jr. Trust in which Mr. Perkinson is
     deemed to share beneficial ownership and 5,171 shares held as agent for Mr.
     Perkinson's wife. Mr. Perkinson is co-trustee of the Robert E. Perkinson,
     Sr. Trust and holds a remainder interest therein with two of his siblings,
     and he is co-trustee and sole beneficiary of the Robert E. Perkinson, Jr.
     Trust.

(10) Includes 12,241 shares allocated to Mr. Schumacher's ESOP account.

(11) Includes 35,561 shares held by Stafford Farms LLC as to which Mr. Stafford
     is deemed to share beneficial ownership. Also includes 162,632 shares held
     jointly by Mr. Stafford and his wife, and 1,901 shares held by Mr.
     Stafford's wife.

(12) Includes 7,746 shares issuable upon exercise of currently exercisable
     options granted under The CommonWealth Bank Option Plan.

(13) Includes 4,890 shares issuable upon exercise of currently exercisable
     options granted under the Directors' Option Plan.

REPORT ON EXECUTIVE COMPENSATION

     The Board of Directors maintains a 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"). The Committee also periodically reviews the compensation of other
executive officers named in the Summary Compensation Table subject to primary
salary administration for these officers by the CEO.

     Other responsibilities of the Compensation Committee include the
development of proposed contractual terms of employment and establishment of a
framework for a competitive compensation package for the CEO and long-term
compensation programs for all executive officers that adequately reward
performance and provide 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 CEO as
measured against predetermined goals and objectives; iv) comparative performance
of the CEO as benchmarked against peer groups of comparable commercial banks;
and v) the achievement of overall corporate goals.

     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 Corporation and the
designated peer group. In performing this analysis, the Committee utilized the
Sheshunoff Executive Compensation Survey and the 2003 SNL Executive Compensation
Review as well as compensation data from other specifically identified banking
peers.

     In review of cash compensation of the CEO for the 2003 fiscal year, the
committee awarded a merit increase which resulted in a total increase in base
compensation from $244,800 to $274,800 annually. This salary adjustment was
effective January 1, 2003.

     In 2003 there were no recommended changes in the employment contract of the
CEO. The CEO employment contract is for a three year term and renews annually.
The contract 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

     For 2003 the Committee recommended to the Board of Directors a tiered
incentive compensation strategy for the CEO based upon the Corporation's ability
to meet specific financial benchmarks. The actual bonus payment to the CEO in
the first quarter of 2003 was $125,000.

                                        8


     This report shall not be deemed to be incorporated by reference into any
filing under the Securities Act of 1933 (the "Securities Act") or the Exchange
Act, unless the Corporation specifically incorporates this report by reference
and shall not otherwise be deemed filed under the Securities Act or the Exchange
Act.

                                          Allen T. Hamner
                                          A. A. Modena
                                          William P. Stafford, II.

COMPENSATION COMMITTEE INTERLOCKS AND INSIDER PARTICIPATION

     No member of the Compensation Committee of the Board of Directors is an
officer or employee of the Corporation. No member of the Committee or executive
officer of the Corporation has a relationship that would constitute an
interlocking relationship with executive officers or directors of another
entity.

REPORT OF THE AUDIT COMMITTEE

     The Audit Committee of the Board is responsible for providing independent,
objective oversight of the Corporation's accounting functions, financial
reporting process and internal controls. The Audit Committee operates under a
written charter, which has been revised and approved by the Corporation's Board
of Directors to comply with the Sarbanes-Oxley Act of 2002.

     The responsibilities of the Audit Committee include the appointment of an
accounting firm to be engaged as the Corporation's independent auditors for the
purpose of performing an audit of the Corporation's financial statements and
expressing an opinion as to the conformity of such financial statements with
accounting principles generally accepted within the United States. Additionally,
and as appropriate, the Audit Committee reviews, evaluates, discusses, and
consults with management, internal audit personnel and the independent auditors
regarding the following:

     - the plan for, and independent auditors' report on, each audit of the
       Corporation's financial statements

     - the Corporation's financial disclosure documents, including all financial
       statements and reports sent to shareholders

     - changes in the Corporation's accounting practices, principles, controls
       or methodologies, or in its financial statements

     - significant developments in accounting rules

     - the adequacy of the Corporation's internal accounting controls, and
       accounting, financial and auditing personnel

     - the establishment and maintenance of an environment at the Corporation
       that promotes ethical behavior

     The Audit Committee Charter incorporates standards set forth in Securities
and Exchange Commission regulations and the listing standards of the National
Association of Securities Dealers. After appropriate review and discussion, the
Audit Committee determined that the Committee fulfilled its responsibilities
under the Audit Committee Charter in 2003.

     The Audit Committee is responsible for recommending to the Board that the
Corporation's financial statements be included in its annual report. The
Committee held ten meetings during the fiscal year 2003 and took a number of
steps in making the independent auditor recommendation. First, the Audit
Committee discussed with its independent auditors those matters the independent
auditor communicated to and discussed with the Audit Committee under applicable
auditing standards, including information regarding the scope and results of the
audit. These communications and discussions are intended to assist the Audit
Committee in overseeing the financial reporting and disclosure process. Second,
the Audit Committee discussed the external auditor's independence with that firm
and received a letter from the external auditor concerning independence as
required under applicable independence standards for auditors of public
companies. This discussion and disclosure informed the Audit Committee of the
external auditors' independence, and assisted the Audit Committee in evaluating
such independence. Finally, the Audit Committee reviewed and discussed, with the
Corporation
                                        9


management and the accounting firm, the Corporation's audited consolidated
balance sheet at December 31, 2003 and consolidated statement of income, cash
flows and stockholders' equity for the year then ended. Based on discussions
with the external auditors concerning the audit, the independence discussions,
and the financial statement review, and such other matters deemed relevant and
appropriate by the Audit Committee, the Audit Committee recommended to the Board
(and the Board approved) that these financial statements be included in the
Corporation's 2003 Annual Report to Shareholders and incorporated by reference
in its Annual Report on Form 10-K filed with the Securities and Exchange
Commission.

     This report shall not be deemed to be incorporated by reference into any
filing under the Securities Act or the Exchange Act, unless the Corporation
specifically incorporates this report by reference, and shall not otherwise be
deemed filed under the Securities Act or the Exchange Act.

                                          Robert E. Perkinson, Jr., Audit
                                          Committee Chair
                                          B. W. Harvey, Audit Committee Member
                                          Allen T. Hamner, Audit Committee
                                          Member

EXECUTIVE COMPENSATION FOR THE YEARS ENDED DECEMBER 31, 2003, 2002 AND 2001

     The following Summary Compensation Table sets forth 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
year ended December 31, 2003.

                           SUMMARY COMPENSATION TABLE



                                                                                   LONG-TERM
                                                                                  COMPENSATION
                                                                              --------------------
                                                                                AWARDS     PAYOUTS
                                                                              ----------   -------
NAME OF INDIVIDUAL/                                          OTHER ANNUAL     SECURITIES    LTIP        ALL OTHER
CAPACITIES SERVED             YEAR    SALARY     BONUS     COMPENSATION (1)    OPTIONS     PAYOUTS   COMPENSATION (2)
-------------------           ----   --------   --------   ----------------   ----------   -------   ----------------
                                                                                
John M. Mendez..............  2003   $266,932   $125,000         $ --          $14,108      $ --         $104,498
President &                   2002   $228,184   $ 36,000         $ --           14,108      $ --         $ 51,430
Chief Executive Officer       2001   $224,105   $ 30,000         $ --           14,108      $ --         $ 48,794
of the Corporation;
Executive Vice President of
First Community Bank, N. A.

Robert L. Buzzo.............  2003   $149,200   $ 20,000         $ --            7,565      $ --         $ 58,854
Vice President and            2002   $135,678   $ 11,221         $ --            7,565      $ --         $ 38,533
Secretary of the              2001   $122,069   $ 14,751         $ --            7,565      $ --         $ 34,741
Corporation; President of
First Community Bank, N. A.;
Chief Executive Officer of
the Bluefield Division of
First Community Bank, N. A.

E. Stephen Lilly............  2003   $162,200   $ 25,000         $ --          $ 7,550      $ --         $ 53,823
Chief Operating Officer       2002   $138,669   $ 14,632         $ --            7,550      $ --         $ 33,970
of the Corporation;           2001   $121,618   $ 30,092         $ --            7,550      $ --         $ 33,484
Senior Vice President &
Chief Operating Officer of
First Community Bank, N. A.

Robert L. Schumacher........  2003   $124,000   $ 20,000         $ --            9,266      $ --         $ 32,057
Chief Financial Officer       2002   $104,391   $ 10,827         $ --            9,266      $ --         $ 27,002
of the Corporation;           2001   $ 99,047   $  8,622         $ --            9,266      $ --         $ 24,825
Senior Vice
President-Finance and
Secretary of First Community
Bank, N. A.


                                        10


(1) The Corporation provides perquisites to the named officers, comprised of
    dues for country club membership and the personal use of Corporation
    vehicles. The value of such benefits do not exceed the lesser of $50,000 or
    10% of salary and bonus for any of the named officers.

(2) Includes $12,000, $7,200, $7,800 and $6,000 in 401(k) matching contributions
    for Messrs. Mendez, Buzzo, Lilly and Schumacher, respectively, for 2003.
    Includes $11,000, $10,271, $11,000 and $8,525 in ESOP contributions for
    Messrs. Mendez, Buzzo, Lilly and Schumacher, respectively, for 2003.
    Includes $12,000, $7,200, $7,800 and $6,000 in 401(k) deferrals for Messrs.
    Mendez, Buzzo, Lilly and Schumacher, respectively, for 2003. Includes
    $7,998, $10,800, $7,800 and $6,000 in Wrap Plan deferrals for Messrs.
    Mendez, Buzzo, Lilly and Schumacher, respectively, for 2003. Includes
    $19,550, $4,005, $4,718 and $3,300 in Wrap Plan contributions for Messrs.
    Mendez, Buzzo, Lilly and Schumacher, respectively, for 2003. Includes
    $41,950, $19,378, $14,705 and $2,232 in benefit accrual vesting of Executive
    Supplemental Retirement and Retention program benefits for Messrs. Mendez,
    Buzzo, Lilly and Schumacher, respectively, for 2003.

  STOCK OPTIONS

     In 1999, the Corporation instituted a Stock Option Plan (the "Plan") to
encourage and facilitate investment in the Common Stock of the Corporation 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 Corporation'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 332,750 shares. Total
options granted under the Plan at December 31, 2003 represent the right to
acquire an aggregate of 309,349 shares. Under the Plan, an optionee is deemed to
have been granted options in five annual installments on January 1 of each year
beginning January 1, 1999 and continued through 2003. 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 Corporation'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 at or
after age 62, 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.

     In addition, the 2003 acquisition of The CommonWealth Bank added additional
stock options on 120,155 shares (124,380 shares adjusted by the merger
conversion factor of .9015 and the 10% stock dividend in 2003). These options
included awards to employees and directors and were issued by The CommonWealth
Bank in 12 grants beginning in 1994 and ending in 2002 with adjusted exercise
prices ranging from $4.75 to $17.40. These options are fully vested and are
exercisable for up to ten years following the grant date. At December 31, 2003,
70,320 options shares were outstanding and exercisable under the former
CommonWealth Plan.

                                        11


     The following table (on the next page) details options deemed granted to
Executive Officers listed in the Summary Compensation Table and other officers
during 2003 under the above-referenced 1999 Plan.

                   OPTIONS DEEMED GRANTED IN LAST FISCAL YEAR



                                                       INDIVIDUAL GRANTS IN 2003
                              ----------------------------------------------------------------------------
                               NUMBER OF     % OF TOTAL
                              SECURITIES      OPTIONS
                              UNDERLYING     GRANTED TO    EXERCISE OR
                                OPTIONS     EMPLOYEES IN   BASE PRICE     EXPIRATION        GRANT DATE
NAME                          GRANTED (1)   FISCAL YEAR    ($/SH) (1)      DATES (2)     PRESENT VALUE (3)
----                          -----------   ------------   -----------   -------------   -----------------
                                                                          
John M. Mendez..............    14,108          19.55%        29.15           03/01/22       $ 99,461
Robert L. Buzzo.............     7,565          10.48%        29.15           04/01/17       $ 53,333
E. Stephen Lilly............     7,550          10.46%        29.15           07/01/25       $ 53,228
Robert L. Schumacher........     9,266          12.84%        29.15           04/01/18       $ 65,325
18 Optionees
  (including the 4 listed
  above)....................    72,153         100.00%        29.15      From 05/01/10       $508,679
                                                                           To 05/01/43


(1) Plan participants may use previously owned shares to pay for an option's
    exercise price. Additionally, plan participants may have the Corporation
    withhold their shares due upon exercise of an option to satisfy their
    required tax withholding obligations.

(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. All executive options vest ratably over the seven year period following
    the date of deemed grant as described above.

(3) The grant date present value of options was determined using the
    Black-Scholes model with the following assumptions: risk-free interest rate
    of 4.03%, dividend yield of 2.96%, expected volatility of the market price
    of the Corporation's common stock of 22.8%, and average anticipated time to
    exercise of 11.97 years.

OPTION EXERCISES IN LAST FISCAL YEAR

     The following table sets forth certain information concerning exercises of
stock options by the executive officers listed in the Summary Compensation Table
during the fiscal year ended December 31, 2003 and options held at December 31,
2003.

                      OPTION EXERCISES IN LAST FISCAL YEAR



                                                       NUMBER OF SECURITIES          VALUE OF UNEXERCISED
                                                      UNDERLYING UNEXERCISED             IN-THE-MONEY
                             SHARES                     OPTONS AT YEAR END          OPTIONS AT YEAR END (1)
                           ACQUIRED ON    VALUE     ---------------------------   ---------------------------
NAME                        EXERCISE     REALIZED   EXERCISABLE   UNEXERCISABLE   EXERCISABLE   UNEXERCISABLE
----                       -----------   --------   -----------   -------------   -----------   -------------
                                                                              
John M. Mendez...........      --          --           --           70,540           --          $878,392
Robert L. Buzzo..........      --          --           --           37,825           --          $471,012
E. Stephen Lilly.........      --          --           --           37,750           --          $470,078
Robert L. Schumacher.....      --          --           --           46,330           --          $576,920


(1) Represents the market value per share of Common Stock at fiscal year-end
    based on its closing price of $33.16 at December 31, 2003, minus the
    exercise price per share of the options outstanding times the number of
    shares of Common Stock represented by such options.

WRAP PLAN

     The Corporation maintains a non-qualified Supplemental 401(k) Plan ("Wrap
Plan") for the purpose of providing deferred compensation which cannot be
accumulated under the Qualified ESOP/401(k) Combined Plan provisions above
because of deferral and covered compensation limitations on tax-qualified
pension plan benefits.
                                        12


The Corporation makes a non-qualified matching credit on employee contributions
at the rate established in the 401(k) Plan (100% in 2003) of up to 6% of
compensation deferred and also makes contributions in lieu of Qualified ESOP
contributions for compensation in excess of the $200,000 compensation limit.
Contributions under the Wrap Plan in 2003 for the covered persons are included
in the Summary Compensation Table and are as follows: Mendez -- $19,550;
Buzzo -- $4,005; Lilly -- $4,718; and Schumacher -- $3,300.

EXECUTIVE RETENTION PLAN

     In 1999, the Corporation 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
62) targeted at 15% of final compensation projected at an assumed 3% salary
progression rate. Benefits under the Executive Retention Plan become payable at
Normal Retirement age 62 or at Early Retirement age 60. Actual benefits payable
under the Executive Retention Plan are dependent on an indexed retirement
benefit formula that accrues benefits equal to the aggregate after-tax income of
associated life insurance contracts less the Corporation's tax-effected cost of
funds for that plan year. Benefits under the Executive Retention Plan are
dependent on the performance of the insurance contracts and are not guaranteed
by the Corporation.

     In connection with the Executive Retention Plan, the Corporation 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 Corporation 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 Executive Retention Plan. The Corporation
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 Executive 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.

     During 2003 the vesting schedule under the plan was amended to provide for
graded vesting of benefits. Benefits under the Executive Retention Plan, which
begin to accrue with respect to years of service under the Plan, vest 25% after
five years, 50% after ten years, 75% after 15 years, and an additional 5% per
year thereafter, with vesting accelerated to 100% at age 62. Prior to the
amendment, the Plan provided no benefits if termination of employment occurred
prior to age 62.

DIRECTORS' SUPPLEMENTAL RETIREMENT PLAN

     In 2001, the Corporation established a Directors' Supplemental Retirement
Plan for its non-employee Directors. This Plan provides for a benefit upon
retirement from service on the Board at specified ages depending upon length of
service or death. Benefits under the Supplemental Retirement Plan become payable
at age 70, 75 and 78 depending upon the individual director's age and original
date of election to the Board. Actual benefits payable under the Supplemental
Retirement Plan are dependent on an indexed retirement benefit formula that
accrues benefits equal to the aggregate after-tax income of associated life
insurance contracts less the Corporation's tax-effected cost of funds for that
plan year. Benefits under the Supplemental Retirement Plan are dependent on the
performance of the insurance contracts and are not guaranteed by the
Corporation.

     In connection with the Directors' Supplemental Retirement Plan, the
Corporation has also entered into Life Insurance Endorsement Method Split Dollar
Agreements (the "Agreements") with certain directors covered under the Plan.
Under the Agreements, the Corporation 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 Supplemental
Retirement Plan. The Corporation 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 Supplemental Retirement Plan also contains provisions for change of
control, as defined, which allow the Directors to retain benefits under the Plan
in the event of a termination of service, other than for cause, during

                                        13


the twelve months prior to a change in control or anytime thereafter, unless the
Director voluntarily terminates his service within 90 days following the change
in control.

     Because the Supplemental Retirement Plan was designed to retain the future
services of Directors, no benefits are payable under the Plan in the event of
voluntary or involuntary termination prior to retirement age as defined in the
Plan document.

INDEMNIFICATION OF DIRECTORS AND CERTAIN OFFICERS

     During 2003 the Corporation and its subsidiary bank adopted Indemnification
Agreements for all Directors and Certain Officers, which provide a process for
the request and grant of indemnification under circumstances provided for under
the Corporation Articles of Association and By-laws. The agreements spell out
notice provisions, rights and responsibilities of the Corporation and the
indemnitee. The full text of one of these agreements for the Corporation and one
for its banking subsidiary are included as Exhibits 10.10 and 10.11 of the
Company's Annual Report on Form 10-K for 2003.

                                        14


COMPARATIVE PERFORMANCE OF THE CORPORATION

     The following chart was compiled by SNL Securities, LC and compares
cumulative total shareholder return on the Corporation's Common Stock for the
five-year period ended December 31, 2003 with cumulative total shareholder
return of: (1) The Standard & Poor's 500 market index ("S&P 500"); and (2) a
group of 23 Peer Bank Holding Companies (Asset Size & Regional Peer Group).

                        FIRST COMMUNITY BANCSHARES, INC.

     The graph assumes an initial investment of $100 on December 31, 1998 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 stock at the then current market value.

                               Performance Graph



--------------------------------------------------------------------------------------------------------------
                                                                    PERIOD ENDING
                                       -----------------------------------------------------------------------
INDEX                                   12/31/98    12/31/99    12/31/00    12/31/01    12/31/02    12/31/03
--------------------------------------------------------------------------------------------------------------
                                                                                 
 First Community Bancshares, Inc.        100.00       81.41       83.85      144.58      171.54      209.49
--------------------------------------------------------------------------------------------------------------
 S&P 500*                                100.00      121.11      110.34       97.32       75.75       97.40
--------------------------------------------------------------------------------------------------------------
 Asset Size & Regional Peer Group**      100.00       82.35       73.54       90.30      123.96      164.02
--------------------------------------------------------------------------------------------------------------


 * Source: CRSP, Center for Research in Security Prices, Graduate School of
   Business, The University of Chicago 2004. Used with permission. All rights
   reserved. crsp.com.

** The Asset Size & Regional Peer Group consists of banks that are traded on the
   NASDAQ, pink sheet, and bulletin board exchanges, have total assets between
   $1B and $5B, and are in the Southeast region.

                                        15


                  2.  RATIFICATION OF 2004 OMNIBUS STOCK PLAN

     At its regularly scheduled meeting in January, 2004 the Board of Directors
adopted the 2004 Omnibus Stock Option Plan ("2004 Plan") of the Corporation
subject to approval by the stockholders of the Corporation at the Annual
Meeting. The following general description of certain features of the 2004 Plan
is qualified in its entirety by reference to the governing 2004 Plan document, a
copy of which is attached hereto as Annex B.

                     PURPOSE OF THE 2004 OMNIBUS STOCK PLAN

     The purposes of the 2004 Plan are to enable the Corporation to promote the
long-term success of the Corporation and create shareholder value by (a)
encouraging officers, employees, directors and individuals performing services
for the Corporation as consultants or independent contractors to focus on
critical long-range objectives, (b) encouraging the attraction and retention of
officers, employees, directors, consultants and independent contractors with
exceptional qualifications, and (c) linking officers, employees, directors,
consultants and independent contractors directly to shareholder interests
through ownership of the Corporation. The 2004 Plan seeks to achieve these
purposes by providing for Awards in the form of options to purchase shares of
the Corporation and outright grants of shares to designated individuals. The
2004 Plan has been prepared to comply with all applicable tax and securities
laws, including Section 16(b) of the Exchange Act and state and Federal tax
laws.

                   DESCRIPTION OF THE 2004 OMNIBUS STOCK PLAN

GENERAL

     The following general description of certain features of the 2004 Plan is
qualified in its entirety by reference to the 2004 Plan which will be made
available upon request. Officers, directors, employees and other persons who are
designated by the Compensation Committee will be eligible to receive, at no cost
to them, awards under the 2004 Plan (the "2004 Optionees"). Each award granted
pursuant to the 2004 Option Plan shall be evidenced by an instrument in such
form as the Compensation Committee shall from time to time approve. It is
anticipated that awards granted under the 2004 Option Plan would constitute
either Incentive Stock Options (options meeting the requirements under Section
422 of the Internal Revenue Code of 1986, as amended ("Code"), Non-Qualified
Stock Options, Restricted Stock Awards or Performance Awards. Option shares may
be paid for in cash, shares of Common Stock, or a combination of both.
Restricted Stock Award shares would, upon the lapse of any applicable
restrictions imposed under the instrument, be made available to the grantee. The
Corporation will receive no monetary consideration for the granting of awards
under the 2004 Option Plan. Further, the Corporation will receive no
consideration other than the option exercise price per share for Common Stock
issued to 2004 Optionees upon the exercise of their options.

     Shares issuable under the 2004 Option Plan may be from authorized but
unissued shares, treasury shares or shares purchased in the open market. An
award which expires, becomes unexercisable, or is forfeited for any reason prior
to its exercise or the lapse of any applicable restrictions will again be
available for issuance under the 2004 Option Plan. No award or any right or
interest therein is assignable or transferable except by will or the laws of
descent and distribution. The 2004 Option Plan shall continue in effect for a
term of ten years from the 2004 Option Plan effective date.

TYPES OF OPTIONS AND AWARDS

     The Compensation Committee may grant Incentive Stock Options, Non-Qualified
Stock Options, Restricted Stock Awards or Performance Awards. In general, if a
2004 Optionee ceases to serve as an employee of the Corporation for any reason
other than death, retirement or termination of employment due to disability, an
exercisable Incentive Stock Option may continue to be exercisable for three
months but in no event after the expiration date of the option, except as may
otherwise be determined by the Compensation Committee at the time of the award.
In the event of the death of a 2004 Optionee during employment or termination of
employment due to retirement or disability, an exercisable Incentive Stock
Option or Non-Qualified Stock Option will continue to be exercisable for twelve
months, to the extent exercisable by the 2004 Optionee immediately prior to the
2004
                                        16


Optionee's death or termination of employment due to retirement or disability
but only if, and to the extent that, a 2004 Optionee was entitled to exercise
such Incentive Stock Options or Non-Qualified Stock Options on the date of death
or termination of employment due to retirement or disability. Under no
circumstances, however, shall the options of a 2004 Optionee remain exercisable
beyond the remaining term of such options.

     The exercise price for the purchase of Common Stock subject to an Incentive
Stock Option may not be less than one hundred percent (100%) of the Fair Market
Value of the Common Stock covered by the option on the date of grant of such
option. No more than $100,000 of Incentive Stock Options can become exercisable
for the first time in any one year for any one person. The Compensation
Committee may impose additional conditions upon the right of a 2004 Optionee to
exercise any option granted hereunder which are not inconsistent with the terms
of the 2004 Option Plan or the requirements for qualification as an Incentive
Stock Option, if such option is intended to qualify as an Incentive Stock
Option. The exercise price for the purchase of Common Stock subject to a
Non-Qualified Stock Option may be equal to, below or above the Fair Market Value
of the Common Stock covered by the option on the date of grant of such option
and shall be set forth in the individual award agreement governing the terms of
the award. No shares of Common Stock shall be issued upon the exercise of an
option until full payment therefore has been received by the Corporation, and no
2004 Optionee shall have any of the rights of a stockholder of the Corporation
until shares of Common Stock are issued to such 2004.

     The 2004 Option Plan provides that the Board of Directors of the
Corporation may authorize the Compensation Committee to direct the execution of
an instrument providing for the modification, extension or renewal of any
outstanding option, provided that no such modification, extension or renewal
shall confer on the 2004 Optionee any right or benefit which could not be
conferred on the 2004 Optionee by the grant of a new option at such time, and
shall not materially decrease the 2004 Optionee's benefits under the option
without the 2004 Optionee's consent, except as otherwise provided under the 2004
Option Plan.

NUMBER OF SHARES COVERED BY THE 2004 OMNIBUS STOCK PLAN

     A total of 200,000 shares of Common Stock, which is equal to 1.78% of the
outstanding stock is reserved for future issuance pursuant to the 2004 Plan. If
any recapitalization, reclassification, stock dividend, stock split, reverse
stock split, or other distribution with respect to the Common Stock or other
change in corporate structure affecting the Common Stock occurs, the Board of
Directors may, in the manner and to the extent it deems appropriate and
equitable and consistent with the terms of the 2004 Plan, cause an adjustment to
be made in (i) the maximum number of shares available under the 2004 Plan; (ii)
the number of shares or other rights subject to outstanding Awards; (iii) the
price for each share or other right subject to an outstanding Award; or (4) any
of the terms affected by the event.

AWARD GRANTS UNDER THE 2004 OMNIBUS STOCK PLAN

     The Board or the Compensation Committee shall from time to time determine
the officers, directors, employees and other persons who shall be granted
options, Restricted Stock Awards or Performance Awards under the 2004 Option
Plan, the number of options or restricted or performance shares to be granted to
any individual, and with respect to options, whether the options granted will be
Incentive Stock Options and/or Non-Qualified Stock Options. In selecting 2004
Optionees and in determining the number of options to be granted, the Board or
the Compensation Committee may consider the nature of the services rendered by
each such individual, each individual's current and potential contribution to
the Corporation and such other factors as may be deemed relevant. The 2004
Optionees may, if otherwise eligible, be granted additional options subject to
any applicable statutory limitations on such grants.

     Option awards shall become vested so that 25% of an option award shall vest
as of the date of the grant and 25% of the option award shall vest on each one
year anniversary thereafter so that 100% of the option award shall be vested as
of the third anniversary of the grant, unless otherwise determined in the
discretion of the Board and memorialized in the governing stock award agreement.
No vesting shall occur on or after the date that an optionee's employment or
personal services contract with the Corporation terminates for any reason other
than his death, retirement or termination of employment due to disability.
Notwithstanding the foregoing, in the event of an optionee's death during
employment or termination of employment due to disability, any awards granted to

                                        17


him not yet vested on that date shall become 100% vested as of such date and
shall be exercisable by the optionee or his personal representative in
accordance with the terms of the 2004 Option Plan. In the event of a 2004
Optionee's retirement, any awards granted to him not yet vested on that date
shall become 100% vested and exercisable only if the grant date of such awards
precedes the optionee's date of retirement by two or more years.

ADJUSTMENTS

     Subject to any required action by the stockholders of the Corporation,
within the sole discretion of the Compensation Committee, the aggregate number
of shares of Common Stock for which options may be granted hereunder or the
number of shares of Common Stock represented by each outstanding option will be
proportionately adjusted for any increase or decrease in the number of issued
and outstanding shares of Common Stock resulting from a subdivision or
consolidation of shares or the payment of a stock dividend or any other increase
or decrease in the number of shares of Common Stock effected without the receipt
or payment of consideration by the Corporation. However, no action may be taken
by the Compensation Committee which would cause Incentive Stock Options granted
pursuant to the 2004 Option Plan to fail to meet the

AMENDMENT AND TERMINATION OF THE 2004 OMNIBUS STOCK PLAN

     The Board of Directors may alter, suspend or discontinue the 2004 Option
Plan, except that no action of the Board shall increase the maximum number of
shares of Common Stock issuable under the 2004 Option Plan, materially increase
the benefits accruing to 2004 Optionees under the 2004 Option Plan or materially
modify the requirements for eligibility for participation in the 2004 Option
Plan unless such action of the Board shall be subject to approval or
ratification by the stockholders of the Corporation.

POSSIBLE DILUTIVE EFFECTS OF THE 2004 OMNIBUS STOCK PLAN

     The Common Stock to be issued upon the exercise of options awarded under
the 2004 Option Plan may either be authorized but unissued shares of Common
Stock or shares purchased in the open market. Because the stockholders of the
Corporation do not have preemptive rights, to the extent that the Corporation
funds the 2004 Option Plan, in whole or in part, with authorized but unissued
shares, the interests of current stockholders may be diluted. The Corporation
can avoid dilution resulting from awards under the 2004 Option Plan by
delivering shares repurchased in the open market upon the exercise of options.

FEDERAL INCOME TAX CONSEQUENCES TO PARTICIPANTS IN 2004 OMNIBUS STOCK PLAN

     The following is a brief summary of certain of the Federal income tax
consequences of certain transactions under the 2004 Option Plan. This summary is
not intended to be exhaustive and does not describe state or local tax
consequences.

     Non-qualified stock options.  Non-qualified stock options granted under the
2004 Option Plan do not qualify as "incentive stock options" and will not
qualify for any special tax benefits to the 2004 Optionee. A 2004 Optionee
generally will not recognize any taxable income at the time he or she is granted
a Non-qualified option. However, upon its exercise, the 2004 Optionee will
recognize ordinary income for Federal income tax purposes measured by the excess
of the then fair market value of the shares over the exercise price. The income
realized by the 2004 Optionee will be subject to income and other employee
withholding taxes. The 2004 Optionee's basis for determination of gain or loss
upon the subsequent disposition of shares acquired upon the exercise of a
Non-qualified stock option will be the amount paid for such shares plus any
ordinary income recognized as a result of the exercise of such option. Upon
disposition of any shares acquired pursuant to the exercise of a Non-qualified
stock option, the difference between the sale price and the 2004 Optionee's
basis in the shares will be treated as a capital gain or loss and generally will
be characterized as long-term capital gain or loss if the shares have been held
for more than one year at their disposition. In general, there will be no
Federal income tax deduction allowed to the Corporation upon the grant or
termination of a Non-qualified stock option or a sale or disposition of the
shares acquired upon the exercise of a Non-qualified stock option. However, upon
the exercise of a Non-qualified stock option, the Corporation will be entitled
to a deduction for Federal income tax

                                        18


purposes equal to the amount of ordinary income that an 2004 Optionee is
required to recognize as a result of the exercise, provided that the deduction
is not otherwise disallowed under the Code.

     Incentive Stock Options.  If an option granted under the 2004 Option Plan
is treated as an incentive stock option, the 2004 Optionee will not recognize
any income upon either the grant or the exercise of the option, and the
Corporation will not be allowed a deduction for Federal tax purposes. Upon a
sale of the shares, the tax treatment to the 2004 Optionee and the Corporation
will depend primarily upon whether the 2004 Optionee has met certain holding
period requirements at the time he or she sells the shares. In addition, as
discussed below, the exercise of an incentive stock option may subject the 2004
Optionee to alternative minimum tax liability. If a 2004 Optionee exercises an
incentive stock option and does not dispose of the shares received within two
years after the date of such option or within one year after the transfer of the
shares to him or her, any gain realized upon the disposition will be
characterized as long-term capital gain and, in such case, the Corporation will
not be entitled to a Federal tax deduction.

     If the 2004 Optionee disposes of the shares either within two years after
the date the option is granted or within one year after the transfer of the
shares to him or her, such disposition will be treated as a disqualifying
disposition and an amount equal to the lesser of (1) the fair market value of
the shares on the date of exercise minus the purchase price, or (2) the amount
realized on the disposition minus the purchase price, will be taxed as ordinary
income to the 2004 Optionee in the taxable year in which the disposition occurs.
However, in the case of gifts, sales to related parties, and certain other
transactions, the full difference between the fair market value of the stock and
the purchase price will be treated as compensation income. The excess, if any,
of the amount realized upon disposition over the fair market value at the time
of the exercise of the option will be treated as long-term capital gain if the
shares have been held for more than one year following the exercise of the
option.

     The exercise of an incentive stock option may subject an 2004 Optionee to
alternative minimum tax liability because the excess of the fair market value of
the shares at the time an incentive stock option is exercised over the purchase
price of the shares is included in income for purposes of the alternative
minimum tax even though it is not included in taxable income for purposes of
determining the regular tax liability of an employee. Consequently, an 2004
Optionee may be obligated to pay alternative minimum tax in the year he or she
exercises an incentive stock option.

     In general, there will be no Federal income tax deductions allowed to the
Corporation upon the grant, exercise or termination of an incentive stock
option. However, in the event an 2004 Optionee sells or disposes of stock
received on the exercise of an incentive stock option in a disqualifying
disposition, the Corporation will be entitled to a deduction for Federal income
tax purposes in an amount equal to the ordinary income, if any, recognized by
the 2004 Optionee upon disposition of the shares, provided that the deduction is
not otherwise disallowed under the Code.

     Restricted Shares.  A recipient of a Restricted Share Award generally will
be subject to tax at ordinary income rates on the fair market value of the
Restricted Shares reduced by any amount paid by the recipient at such time as
the shares are no longer subject to a substantial risk of forfeiture or
restrictions on transfer for purposes of Section 83 of the Code. However, a
recipient who so elects under Section 83(b) of the Code within 30 days of the
date of transfer of the shares will recognize ordinary income on the date of
transfer of the shares equal to the excess of the fair market value of the share
(determined without regard to the risk of forfeiture or restrictions on
transfer) over any purchase price paid for the shares. If a Section 83(b)
election has not been made, any non-restricted dividends received with respect
to Restricted Shares that are subject at that time to a risk of forfeiture or
restrictions on transfer generally will be treated as compensation that is
taxable as ordinary income to the recipient.

     Performance Shares.  A recipient of a Performance Share Award generally
will be subject to tax at ordinary income rates on the fair market value of the
Performance Shares reduced by any amount paid by the recipient at such time as
the shares are awarded.

                                        19


STOCKHOLDER RATIFICATION

     Stockholder ratification of the 2004 Option Plan is being sought to qualify
the 2004 Option Plan for the granting of Incentive Stock Options in accordance
with the Code, to enable 2004 Optionees to qualify for certain exempt
transactions related to the short-swing profit recapture provisions of Section
16(b) of the 1934 Act, to meet the requirements under the rules of the Nasdaq
National Market for continued listing of the Corporation's Common Stock and to
meet the requirements for the tax-deductibility of certain compensation items
under Section 162(m) of the Code. An affirmative vote of the holders of a
majority of the total votes cast at the Meeting in person or by proxy is
required to constitute stockholder ratification of this proposal.

     THE BOARD OF DIRECTORS RECOMMENDS A VOTE "FOR" THE RATIFICATION OF THE 2004
OMNIBUS STOCK PLAN.

           3.  RATIFICATION OF THE SELECTION OF INDEPENDENT AUDITORS

     Stockholders are being asked to ratify the selection of Ernst & Young LLP,
as independent auditors of the Corporation and its subsidiaries for the fiscal
year ending December 31, 2004. Ernst & Young served as independent auditors for
the Corporation for the fiscal year ended December 31, 2003. 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 ending December 31, 2004, Ernst
& Young will review the Corporation's annual report 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 ending December 31, 2004. The Board 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 expected to be present at the Annual
Meeting to respond to stockholders' questions and to make a statement if the
representative so desires.

     THE BOARD OF DIRECTORS RECOMMENDS A VOTE FOR THE RATIFICATION OF ERNST &
YOUNG AS THE CORPORATION'S INDEPENDENT AUDITORS FOR THE YEAR ENDING DECEMBER 31,
2004.

FEES FOR SERVICES RENDERED BY PRINCIPAL ACCOUNTANT

     Fees for professional services provided by Ernst & Young LLP, the
Corporation's independent auditor and principal accountant, for the respective
fiscal years ended December 31 are set forth below:



                                                                2003       2002
                                                              --------   --------
                                                                   
Audit Fees..................................................  $274,290   $200,375
Audit-Related Fees..........................................  $  3,390   $  4,203
All Other Fees..............................................        --         --
Tax Fees....................................................        --         --


     Fees for audit services include fees associated with the annual audit, the
reviews of the Corporation's quarterly reports on Forms 10-Q and annual report
on Form 10-K, review of other documents filed with the Securities and Exchange
Commission and required statutory audits. Audit related fees primarily include
fees paid for certain accounting consultations. As indicated above, no fees were
paid related to tax or any other services.

PRE-APPROVAL POLICIES AND PROCEDURES

     The Audit Committee has adopted a policy that requires advance approval of
all audit, audit-related, tax services, and other services performed by the
independent auditor. The policy provides for pre-approval by the Audit Committee
of specified audit and non-audit services. Unless the specific service has been
previously pre-

                                        20


approved with respect to that year, the Audit Committee must approve the
permitted service before the independent auditor is engaged to perform it. The
Audit Committee has delegated to the Chair of the Audit Committee authority to
approve permitted services provided that the Chair reports any decisions at its
next scheduled meeting.

                                 OTHER MATTERS

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

                                 ANNUAL REPORTS

     A copy of the Corporation's Form 10-K for the year ended December 31, 2003
accompanies this Proxy Statement. Such report is not part of the proxy
solicitation materials.

     Upon receipt of a written request, the Corporation will furnish to any
stockholder without charge a copy of the Corporation's Annual Report on Form
10-K for fiscal 2003 required to be filed under the Exchange Act. Such written
requests should be directed to the Chief Financial Officer, First Community
Bancshares, Inc., P. O. Box 989, One Community Place, Bluefield Virginia 24605.
The Form 10-K is not part of the proxy solicitation materials.

                            STOCKHOLDERS' PROPOSALS

     Shareholders may communicate with the Board of Directors, including the
non-management director, by sending a letter to the First Community Bancshares,
Inc. Board of Directors, c/o Corporate Secretary, First Community Bancshares,
Inc., P.O. 989, Bluefield, Virginia 24605-0989. The Corporate Secretary has the
authority to disregard any inappropriate communications or to take other
appropriate actions with respect to any such inappropriate communications. If
deemed an appropriate communication, the Corporate Secretary will submit your
correspondence to the Chairman of the Board or to any specific director to whom
the correspondence is directed.

     If any stockholder intends to include a proposal in the Corporation's proxy
statement for the 2005 Annual Meeting, such proposal must be submitted to Robert
L. Buzzo, Corporate Secretary, First Community Bancshares, Inc., P.O. Box 989,
Bluefield, Virginia, 24605-0989 and received by the Corporation at its principal
executive offices on or before November 20, 2004. Otherwise, such proposal will
not be considered for inclusion in the Corporation's Proxy Statement for such
meeting. In order to be considered for possible action by stockholders at the
2005 annual meeting of stockholders, stockholder proposals not included in the
Corporation's proxy statement must be submitted to Robert L. Buzzo, Corporate
Secretary, at the address set forth above, no later than February 3, 2005.

     You are urged to properly complete, execute and return the enclosed form of
proxy or vote via the Internet or toll free number provided elsewhere in the
proxy material.

                                          By Order of the Board of Directors

                                          /s/ Robert L. Buzzo
                                          Robert L. Buzzo, Secretary to the
                                          Board

March 20, 2004
                                        21


                                                                         ANNEX A

                        FIRST COMMUNITY BANCSHARES, INC.

                          NOMINATING COMMITTEE CHARTER

     1. MEMBERS. The members of the committee shall be elected by the board and
shall serve until their successors shall be duly elected and qualified or until
their earlier resignation or removal. All committee members must be independent
directors. The committee shall be composed of no less than three members.

     2. PURPOSES, DUTIES, AND RESPONSIBILITIES.

     The committee helps ensure that the board performs effectively, with
specific responsibility for making recommendations to the board on board
organization and procedures, performance evaluation of the board, and nomination
of directors. This committee works closely with the CEO and the chairman of the
board.

          DUTIES:

          1. Review with the board on an annual basis the appropriate skills and
     characteristics required on the board in the context of the strategic
     direction of the Corporation.

          2. Manage the process whereby the full board annually assesses its
     performance, and then report the results of this evaluation to the board
     along with any recommendations for improvements.

          3. Recommend for board approval a definition of what constitutes an
     independent director. The definition should be in compliance with relevant
     standards by regulators and listing bodies.

          4. Recommend to the board the existing board members to be
     re-nominated, after considering the appropriate skills and characteristics
     required on the board, the current makeup of the board, and the wishes of
     existing board members to be re-nominated.

          5. Review with the board on an annual basis the appropriate skills and
     characteristics required of new board members.

          6. Solicit nominations for new directors and screen the list of
     potential new directors submitted to it by other directors or any other
     sources. Decide whether the assistance of a search firm is needed, and, if
     so, chose the firm. This committee shall have the sole authority to retain
     and terminate any search firm to be used to identify director candidates,
     including sole authority to approve the search firm's fees and other
     retention terms.

          7. After a review of board candidates and after considering the advice
     of the chairman of the board and the CEO, designate which candidates are to
     be interviewed. Candidates at a minimum are interviewed by the chairman of
     the nominating committee, the chairman of the board, and the CEO, but may
     be interviewed by other directors.

          8. After the interviews, recommend for board approval any new
     directors to be nominated. Prior to the final vote of the board on the
     nomination of a new director, arrange for the selected candidate to meet
     all existing directors not yet met.

          9. Design an orientation program for new directors and consult with
     them on their progress.

          10. Review annually the membership guidelines and committee charter
     and recommend to the board any needed changes.

          11. Keep abreast of the developments in the corporate governance field
     that might affect the Corporation.

          12. Consideration of shareholder communications and proposals, if and
     when submitted, according to established process and guidelines.

     This committee has the power to delegate aspects of its work to
     subcommittees, with board approval. Furthermore, the board may allocate any
     of the responsibilities of this committee to a separate committee, provided
     that the committee is composed of independent directors. Any such committee
     must have a published committee charter.

                                       A-1


                                                                         ANNEX B

                        FIRST COMMUNITY BANCSHARES, INC.

                         2004 OMNIBUS STOCK OPTION PLAN

                                   ARTICLE I

                           ESTABLISHMENT OF THE PLAN

     First Community Bancshares, Inc. (the "Company" or "Bancshares") hereby
establishes the First Community Bancshares, Inc. 2004 Omnibus Stock Option Plan
(the "Plan") upon the terms and conditions hereinafter stated. The Purpose of
the Plan is to promote the long-term success of the Company and the creation of
shareholder value by (a) encouraging officers, employees, directors and
individuals performing services for the Company as consultants or independent
contractors to focus on critical long-range objectives, (b) encouraging the
attraction and retention of officers, employees, directors, consultants and
independent contractors with exceptional qualifications, and (c) linking
officers, employees, directors, consultants and independent contractors directly
to shareholder interests through ownership of the Company. The Plan seeks to
achieve this purpose by providing for Awards in the form of options to purchase
shares of the Company.

                                   ARTICLE II

                                  DEFINITIONS

     2.01 "Award" means any stock option granted to a Participant under the
Plan.

     2.02 "Board" means the Board of Directors of the Company.

     2.03 "Code" means the Internal Revenue Code of 1986, as amended.

     2.04 "Common Stock" means shares of the common stock, $1.00 par value per
share, of the Company.

     2.05 "Disability" means any physical or mental impairment which qualifies
an Employee for disability benefits under any applicable long-term disability
plan maintained by the Company or, if no such plan applies, which would qualify
such Employee for disability benefits under the Federal Social Security System.

     2.06 "Effective Date" means the date upon which the Board approves this
Plan.

     2.07 "Employee" means any person who is employed by the Company or a
subsidiary thereof, and whose wages are reported on a Form W-2. The Company
classification as to who is an Employee shall be determinative for purposes of
an individual's eligibility under the Plan.

     2.08 "Exchange Act" means the Securities Exchange Act of 1934, as amended.

     2.09 "Fair Market Value" of a share of the Company's Common Stock for all
purposes under the Plan on a particular date shall be the most recent valuation
adopted by the Board in good faith of the fair market value of each share of the
Company's Common Stock; provided that, in the event the Common Stock becomes
registered under Section 12 or Section 15 of the Exchange Act, the Fair Market
Value of the Company' Common Stock shall be the mean between the high and low
sales price per share of Common Stock on such date, or in case no such sale
takes place on such date, the last date on which a sale occurred, in either case
as reported in the principal consolidated transaction reporting system with
respect to securities listed or admitted to trading on a national securities
exchange or included for quotation on the Nasdaq market, or if the Common Stock
is not listed or admitted for trading or included for quotation, in the
over-the-counter market, as reported by the NASD Automatic Quotation System or,
if such system is no longer in use, the principal other automated quotations
system that may then be in use or, if the Common Stock is not quoted by any such
organization, the average of the closing bid and asked prices as furnished by a
professional market maker making a market in the Common Stock, or such other
method of valuation as may be selected by the Board in good faith.

                                       B-1


     If the relevant date is not a trading day, the determination shall be made
as of the next preceding trading day. As used herein, the term "trading day"
means a day on which public trading of securities occurs and as reported in the
principal consolidated reporting system referred to above, or if the Common
Stock is not listed or admitted to trading on a national securities exchange or
included for quotation on the Nasdaq National Market, any business day.

     2.10 "Grantee" refers to any Participant in the Plan who receives an Award.

     2.11 "Incentive Stock Option" means any Award granted under this Plan which
the Board intends (at the time it is granted) to be an incentive stock option
within the meaning of Section 422 of the Code. All Incentive Stock Options
issued under this Plan are intended to comply with the requirements of Section
422 of the Code, and the regulations thereunder, and all provisions hereunder
shall be read, interpreted and applied with that purpose in mind.

     2.12 "Non-Qualified Stock Option" means any Award granted under this Plan
which is a stock option but is not an Incentive Stock Option.

     2.13 "Officer" means any Employee of the Company or any of its subsidiaries
who is designated by the Board as a corporate officer.

     2.14 "Participant" means any Employee, Officer, director, consultant or
independent contractor who is designated by the Board pursuant to Article VI to
participate in the Plan.

     2.15 "Retirement" means a termination of employment which constitutes a
"retirement" under any applicable qualified pension benefit plan maintained by
the Company as that term is defined by the Employee Retirement Income Security
Act of 1974, as amended ("ERISA") or if no such plan is maintained by the
Company, a termination of employment anytime following attainment of age 65.

     2.16 "Sale Event" means the consummation of (i) a dissolution or
liquidation of the Company, (ii) the sale of all or substantially all of the
assets of the Company to an unrelated person or entity, (iii) a merger,
reorganization or consolidation in which the holders of the Company's
outstanding voting power immediately prior to such transaction do not own a
majority of the outstanding voting power of the surviving or resulting entity
immediately upon completion of such transaction, or (iv) any other transaction
in which the owners of the Company's outstanding voting power prior to such
transaction do not own at least a majority of the outstanding voting power of
the relevant entity after the transaction, in each case, regardless of the form
thereof.

     2.17 "Stock Award Agreement" means the written agreement pursuant to
Article VI hereof that sets forth the terms, conditions, restrictions and
privileges for an Award and that incorporates the terms of the Plan.

                                  ARTICLE III

                  ADMINISTRATION OF THE PLAN AND MISCELLANEOUS

     3.01 Plan Administration. The Plan shall be administered by the
Compensation Committee (the "Committee"). The Committee shall be responsible to
the Board for the overall administration and operation of the Plan, although the
Committee may, in its discretion, delegate to one or more officers
responsibility for the day-to-day operation of the Plan. The Board shall make
all determinations with respect to participation in the Plan by Employees,
Officers, directors, consultants or independent contractors of the Company or
any of its subsidiaries, and with respect to the extent of that participation.
The interpretation and construction of any provision of the Plan by the Board or
the Committee shall be final. No member of the Board shall be liable for any
action or determination made by him or her in good faith

     3.02 Revocation for Misconduct. Any Award, or portion thereof, under this
Plan, whether or not vested, made to a Participant who is discharged from the
employ of the Company or any of its subsidiaries (or whose personal services
contract is terminated in the case of a consultant or independent contractor)
shall automatically terminate, rescind and be revoked.

                                       B-2


     3.03 Limitation on Liability. No Board or Committee member shall be liable
for any action or determination made in good faith with respect to the Plan. To
the maximum extent allowed by law and the Company's bylaws, the Board and the
Committee shall be indemnified by the Company in respect of all their activities
under the Plan.

     3.04 Compliance with Law and Regulations. All Awards granted hereunder
shall be subject to all applicable federal and state laws, rules and regulations
and to such approvals by any government or regulatory agency as may be required.
The Company shall not be required to issue or deliver any certificates for
shares of Common Stock prior to the completion of any registration or
qualification of or obtaining of consents or approvals with respect to such
shares under any Federal or state law or any rule or regulation of any
government body, which the Company shall, in its sole discretion, determine to
be necessary or advisable.

     3.05 Restrictions on Transfer. The Company shall place a legend upon any
certificate representing shares acquired pursuant to an Award granted hereunder
noting that the transfer of such shall may be restricted as permitted by
applicable laws and regulations.

     3.06 Market Stand-Off. In connection with any underwritten public offering
by the Company of its equity securities pursuant to an effective registration
statement filed under the Securities Act, Participants shall not directly or
indirectly sell, make any short sale of, loan, hypothecate, pledge, offer, grant
or sell any option or other contract for the purchase of, purchase any option or
other contract for the sale of, or otherwise dispose of or transfer, or agree to
engage in any of the foregoing transactions with respect to, any common stock
received pursuant to the Plan without the prior written consent of the Company.
Such restriction (the "Market Stand-Off") shall be in effect for a period of
time following the date of the final prospectus for the offering as may be
requested by the Company or its underwriters. In the event of the declaration of
a stock dividend, a spin-off, a stock split, an adjustment in conversion ratio,
a recapitalization or a similar transaction affecting the Company's outstanding
securities without receipt of consideration, any new, substituted or additional
securities which are by reason of such transaction distributed with respect to
any common stock subject to the Market Stand-Off, or into which such common
stock thereby become convertible, shall immediately be subject to the Market
Stand-Off. In order to enforce the Market Stand-Off, the Company may impose
stop-transfer instructions with respect to common stock received pursuant to the
Plan until the end of the applicable stand-off period.

                                   ARTICLE IV

                                  ELIGIBILITY

     Awards may be granted to such Employees, Officers, directors, consultants
or independent contractors as may be designated from time to time by the Board,
pursuant to guidelines, if any, which may be adopted by the Committee from time
to time.

                                   ARTICLE V

                      COMMON STOCK AVAILABLE FOR THE PLAN

     The aggregate number of shares of Common Stock which may be issued pursuant
to this Plan shall be two hundred thousand (200,000). If and to the extent that
the number of issued shares of Common Stock shall be increased or reduced by
change in par value, split up, reclassification, distribution of a dividend
payable in Common Stock, merger, consolidation, reorganization,
recapitalization, reincorporation, or the like, the Board may make appropriate
adjustment in the number of shares of Common Stock authorized by the Plan and in
the number and exercise price of shares covered by outstanding Awards under the
Plan. In the event of any adjustment in the number of shares covered by any
Award, any fractional shares resulting from such adjustment shall be disregarded
and each such Award shall cover only the number of full shares resulting from
such adjustment. The Board may make such adjustments, and its determination
shall be final, binding and conclusive.

     The Board also may adjust the number of shares subject to outstanding
Awards and the exercise price and the terms of outstanding Awards to take into
consideration material changes in accounting practices or principles,
extraordinary dividends, acquisitions or dispositions of stock or property or
any other event if it is determined by
                                       B-3


the Board that such adjustment is appropriate in order to prevent dilution or
expansion of the rights of Participants, provided that no such adjustment shall
be made in the case of an Incentive Stock Option, without the consent of the
participant, if such adjustment would constitute a modification, extension or
renewal of the Option within the meaning of Section 424(h) of the Code.

     No shares shall be the subject of more than one Award at any time, but if
an Award as to any shares is surrendered before exercise, or expires or
terminates for any reason without having been exercised in full, or for any
other reason ceases to be exercisable, the number of shares covered thereby
shall again become available for grant under the Plan as if no Awards had been
previously granted with respect to such shares.

                                   ARTICLE VI

                      PARTICIPATION; STOCK AWARD AGREEMENT

     The Board shall, in its discretion, determine from time to time which
Employees, Officers, directors, consultants or independent contractors will
participate in the Plan and receive Awards under the Plan. In making all such
determinations there shall be taken into account the duties, responsibilities
and performance of each respective Employee, Officer, director, consultant or
independent contractor, his or her present and potential contributions to the
growth and success of the Company, his or her cash compensation and such other
factors as the Board shall deem relevant to accomplishing the purposes of the
Plan.

     Awards may be granted individually or in tandem with other Awards. All
awards are subject to the terms, conditions, restrictions and privileges of the
Plan in addition to the terms, conditions, restrictions and privileges for an
Award contained in the Stock Award Agreement. No Award under this Plan shall be
effective unless memorialized in writing by the Committee in a Stock Award
Agreement delivered to and signed by the Participant.

                                  ARTICLE VII

                                     AWARDS

     7.01 Stock Options. The Board may from time to time grant to eligible
participants Awards of Incentive Stock Options or Non-Qualified Stock Options;
provided however that Awards of Incentive Stock Options shall be limited to
Employees of the Company or any of its subsidiaries. Options intended to qualify
as Incentive Stock Options must have an exercise price at least equal to the
Fair Market Value of a share of Common Stock at the time of grant, except as
provided in Section 8.05. Non-Qualified Stock Options may have an exercise price
that is equal to, below, or above the Fair Market Value of a share of Common
Stock at the time of grant. The exercise price applicable to a particular Award
shall be set forth in each individual Award Agreement.

     7.02 Restricted Stock. The Board may from time to time grant Restricted
Stock Awards to eligible participants in such amounts, on such terms and
conditions, and for such consideration, including no consideration or such
minimum consideration as may be required by law, as it shall determine.

     7.03 Performance Awards. The Board may, in its discretion, grant
performance awards which become payable on account or attainment of one or more
performance goals established by the Board. Performance awards may be paid by
the delivery of Common Stock or cash, or any combination thereof, as determined
in the sole discretion of the Board.

                                  ARTICLE VIII

                                 OPTIONS AWARDS

     8.01 Vesting of Options

     (a) General Rules. Incentive Stock Options and Non-Qualified Stock Options
granted to Participants shall become vested so that 25% of the Option Award
shall vest as of the date of the grant and 25% of the Option Award shall vest on
each one year anniversary thereafter, so that 100% of such Option Award shall be
vested as

                                       B-4


of the third anniversary of the date of grant, unless otherwise determined in
the discretion of the Board and memorialized in the Stock Award Agreement.
Notwithstanding the foregoing, no vesting shall occur on or after the date that
an Employee's employment or personal services contract with the Company or any
of its subsidiaries terminates for any reason other than his Death, Disability
or Retirement. In determining the number of shares of Common Stock with respect
to which such Awards are vested and/or exercisable, fractional shares will be
rounded up to the nearest whole number if the fraction is 0.5 or higher, and
down if it is less.

     (b) Acceleration of Vesting Upon Death, Disability or Retirement. In the
event a Participant dies while in the employ of the Company or any of its
subsidiaries or terminates employment with the Company or any of its
subsidiaries as a result of Disability, any Award(s) granted to such Participant
under this Plan not yet vested on such date shall become 100% vested as of such
date and be exercisable either by the Participant or the Participant's
representative subject to Section 8.03. In the event of a Participant's
Retirement, any Award(s) granted to such Participant under this Plan not yet
vested on such date shall become 100% vested as of such date and become
exercisable only if the grant date of such Award(s) precedes the Participant's
date of Retirement by two (2) or more years.

     8.02 Duration of Options.

     (a) General Rule. Except as provided in Section 8.05, each Award granted to
a Participant shall be exercisable at any time on or after it vests until the
earlier of (i) ten (10) years after its date of grant or (ii) the date that is
six (6) months (ninety (90) days in the case of Incentive Stock Options granted
to Employees) following the last day on which the Participant is employed or
renders services for the benefit of the Company or its subsidiaries.

     (b) Exception for Termination Due to Death, Disability or Retirement. If a
Participant dies while in the employ of the Company or any of its subsidiaries
or terminates employment with the Company or any of its subsidiaries as a result
of death, Disability or Retirement without having fully exercised his Awards,
the Participant or his legal representative or guardian, or the executors,
administrators, legatees or distributes of his estate shall have the right,
during the twelve (12) month period following the earlier of his death
Disability or Retirement, to exercise such Awards to the extent vested on the
date of such death, Disability or Retirement. In no event, however, shall any
Award be exercisable more than ten (10) years from the date it was granted.

     (c) Notice of Disposition; Withholding; Escrow. A Grantee shall immediately
notify the Company in writing of any sale, transfer, assignment or other
disposition (or action constituting a disqualifying disposition within the
meaning of Section 421 of the Code) of any shares of Common Stock acquired
through exercise of an Incentive Stock Option, within two (2) years after the
grant of such Incentive Stock Option or within one (1) year after the
acquisition of such shares, setting forth the date and manner of disposition,
the number of shares disposed of and the price at which such shares were
disposed. The Company shall be entitled to withhold from any compensation or
other payments then or thereafter due to the Grantee such amounts as may be
necessary to satisfy any withholding requirements of Federal or state law or
regulation and, further, to collect from the Grantee any additional amounts
which may be required for such purpose. The Board may, in its discretion,
require shares of Common Stock acquired by a Grantee upon exercise of an
Incentive Stock Option to be held in an escrow arrangement for the purpose of
enabling compliance with the provisions of this Section 8.02(c).

     8.03 Nonassignability. Awards shall not be transferable by a Grantee except
by will or the laws of descent or distribution, and during a Grantee's lifetime
shall be exercisable only by such Grantee or the Grantee's guardian or legal
representative. Notwithstanding the foregoing, or any other provision of this
Plan, a Grantee who holds Non-Qualified Stock Options may transfer such Awards
to his or her spouse, lineal ascendants, lineal descendants, or to a duly
established trust for the benefit of one or more of these individuals. Awards so
transferred may thereafter be transferred only to the Grantee who originally
received the grant or to an individual or trust to whom the Grantee would have
initially transferred the Award pursuant to this Section 8.03. Awards which are
transferred pursuant to this Section 8.03 shall be exercisable by the transferee
according to the same terms and conditions as applied to the Grantee.

     8.04 Manner of Exercise. To the extent vested and exercisable, awards may
be exercised in part or in whole from time to time by execution of a written
notice directed to the Company, at the Company's principal place of

                                       B-5


business, accompanied by cash or a check in payment of the exercise price for
the number of shares specified and paid for. The Board, may in its discretion,
permit a Grantee to exercise vested and exercisable options awarded under this
Plan by surrendering an amount of Common Stock already owned by the Grantee
equal to the options' exercise price, but only in instances where the shares to
be surrendered have been held by the Grantee for a period of at least six (6)
months. Subject to the limitations set forth in the Stock Award Agreement, in
the event of, and after such time as the Common Stock is listed or admitted to
trading on a national securities exchange or included for quotation on the
Nasdaq market, the Board may, in its discretion, allow the Grantee may make
payment by arranging with a third party broker to sell a number of shares
otherwise deliverable to the Grantee and attributable to the exercise of the
Award in order to pay the exercise price of the Award.

     8.05 $100,000 Limitation. Notwithstanding any contrary provisions contained
elsewhere in this Plan and as long as required by Section 422 of the Code, the
aggregate Fair Market Value, determined as of the time an Incentive Stock Option
is granted, of the Common Stock with respect to which Incentive Stock Options
are exercisable for the first time by the Grantee during any calendar year,
under this Plan and stock options that satisfy the requirements of Section 422
of the Code under any other stock option plan or plans maintained by the
Company, shall not exceed $100,000. To the extent that the aggregate value of
shares of common stock to be received by the Grantee for the first time in any
one year pursuant to the exercise of an Incentive Stock Option ("ISO Stock")
exceeds $100,000 based on the fair market value of the Common Stock as of the
date of the Incentive Stock Option's grant, such excess shall be treated as
Common Stock received pursuant to the exercise of a Nonqualified Stock Option
("NQSO Stock"). The Company shall designate which shares of Common Stock to be
received by the Grantee will be treated as ISO Stock and which shares of Common
Stock, if any, will be treated as NQSO Stock by issuing separate share
certificates identifying in the Company's share transfer records which shares
are ISO Stock.

     8.06 Limitation on Ten Percent Stockholders. The price at which shares of
Common Stock may be purchased upon exercise of an Incentive Stock Option granted
to an individual who, at the time such Incentive Stock Option is granted, owns,
directly or indirectly, more than ten percent (10%) of the total combined voting
power of all classes of stock issued to stockholders of the Company, shall be no
less than one hundred and ten percent (110%) of the Fair Market Value of a share
of the Common Stock of the Company at the time of grant, and such Incentive
Stock Option shall by its terms not be exercisable after the expiration of five
(5) years from the date such Incentive Stock Option is granted.

                                   ARTICLE IX

                     AMENDMENT AND TERMINATION OF THE PLAN

     The Board may, by resolution, at any time terminate or amend the Plan with
respect to any shares of Common Stock or Awards which have not been granted, but
no such action shall adversely affect the rights under any outstanding Award
without the holder's consent. If and to the extent necessary to ensure that
Incentive Stock Options granted under the Plan remain qualified under Section
422 of the Code, Plan amendments shall be subject to approval by the Company's
stockholders who are eligible to vote at a meeting of stockholders.

                                   ARTICLE X

                               EMPLOYMENT RIGHTS

     Neither the Plan nor any Award hereunder shall create any right on the part
of any Employee of the Company or any of its subsidiaries to continue in such
capacity.

                                   ARTICLE XI

                                  WITHHOLDING

     The Company may withhold from any cash payment made under this Plan
sufficient amounts to cover any applicable withholding and employment taxes, and
if the amount of such cash payment is insufficient, the

                                       B-6


Company may require the Grantee to pay to the Company the amount required to be
withheld as a condition to delivering the shares acquired pursuant to an Award.
The Company also may withhold or collect amounts with respect to a disqualifying
disposition of shares of Common Stock acquired pursuant to exercise of an
Incentive Stock Option, as provided in Section 8.02(c).

     The Board is authorized to adopt rules, regulations or procedures which
provide for the satisfaction of a Participant's tax withholding obligation by
the retention of shares of Common Stock to which he otherwise would be entitled
pursuant to an Award or by the Participant's delivery of previously-owned shares
of Common Stock or other property. However, if the Company adopts rules,
regulations or procedures which permit withholding obligations to be met by the
retention of Common Stock to which a Grantee otherwise would be entitled
pursuant to an Award, the fair market value of the Common Stock retained for
such purpose shall not exceed the minimum required Federal, state and local tax
withholding due upon exercise of the Award.

                                  ARTICLE XII

                        EFFECTIVE DATE OF THE PLAN; TERM

     12.01 Effective Date of the Plan. This Plan shall become effective on the
Effective Date, and Awards may be granted hereunder as of or after the Effective
Date and prior to the termination of the Plan, provided that no Incentive Stock
Option issued pursuant to this Plan shall qualify as such unless this Plan is
approved by the requisite vote of the holders of the outstanding voting shares
of the Company at a meeting of stockholders of the Company held within twelve
(12) months before or after the Effective Date.

     12.02 Term of Plan. Unless sooner terminated, this Plan shall remain in
effect for a period of ten (10) years ending on the tenth anniversary of the
Effective Date. Termination of the Plan shall not affect any Awards previously
granted and such Awards shall remain valid and in effect until they have been
fully exercised or earned, are surrendered or by their terms expire or are
forfeited.

                                  ARTICLE XIII

                                 GOVERNING LAW

     To the extent not governed by Federal law, this Plan shall be construed
under the laws of the Commonwealth of Virginia.

     IN WITNESS WHEREOF, the Company has caused a duly authorized officer to
execute this First Community Bancshares, Inc. 2004 Omnibus Stock Option Plan,
and to apply the Corporate seal hereto as of the      day of January, 2004.

                                          FIRST COMMUNITY BANCSHARES, INC.

                                          By:
                                          --------------------------------------

                                          Name:
                                          --------------------------------------

                                          Title:
                                          --------------------------------------

                                       B-7



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

The undersigned hereby constitutes and appoints Steven G. Layfield and Jeffrey
L. Farmer, or either of them, attorney and proxy with full power of
substitution, to represent the undersigned at the Annual Meeting of the
Stockholders of First Community Bancshares, Inc. (the "Corporation") to be held
on Tuesday, April 27, 2004, 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 3 directors - Class of 2007         WITHHOLD AUTHORITY
    Allen T. Hamner                                         You may withhold authority to vote for any
    B. W.  Harvey                                           nominee by lining through or otherwise
    John M. Mendez                                          striking out his name.

2.  To ratify the 2004 Omnibus Stock Option Plan.

    FOR           AGAINST         ABSTAIN

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




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:    ________________________, 2004                      ____________________________________
                                                                       SIGNATURE OF STOCKHOLDER

                                                              ____________________________________
                                                                       SIGNATURE OF STOCKHOLDER

                                                              Please check if you plan to attend the
                                                              Stockholders' Meeting on April 27, 2004



In lieu of using this proxy card, you may also vote upon the items set forth
above by entering your voting instructions by telephone at 1-888-216-1279 or on
the world wide web at https//www.proxyvotenow.com/fcb until 11:59 p.m. eastern
daylight time on April 26, 2004. If you wish to use this proxy card, 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.