1

                           SCHEDULE 14A INFORMATION

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


Filed by the Registrant /X/

Filed by a Party other than the Registrant / /

Check the appropriate box:



                                                     
/ /  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 Rule 14a-11(c) or Rule 14a-12


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


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


Payment of Filing Fee (Check the appropriate box):

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

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

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

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

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

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

     (4)  Proposed maximum aggregate value of transaction:

     (5)  Total fee paid:

/ /  Fee paid previously with preliminary materials.

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

     (1)  Amount Previously Paid:

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

     (3)  Filing Party:

     (4)  Date Filed:

* No fee required
   2
 
                               1001 MERCER STREET
                         PRINCETON, WEST VIRGINIA 24740
 
                                 NOTICE OF 1999
                         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 Bluefield Elks Lodge, 1501 Whitethorn Street, Bluefield, West
Virginia, at 3:00 p.m., local time on April 13, 1999, for the purpose of
considering and voting upon the following items as more fully discussed herein.
 
     1. Election of four directors to serve as members of the Board of
        Directors, Class of 2002.
 
     2. Ratification of the selection of Deloitte & Touche, Pittsburgh,
        Pennsylvania, as independent auditors for the year ending December 31,
        1999.
 
     3. Transacting such other business as may properly come before the meeting,
        or any adjournment thereof.
 
     Only stockholders of record at the close of business on March 1, 1999 are
entitled to notice of and to vote at such meeting or at any adjournment thereof.
 
     To ensure your shares are represented at the Annual Meeting, please
complete, sign and return the enclosed proxy as promptly as possible whether or
not you plan to attend the meeting. An addressed return envelope is enclosed for
your convenience. YOU MAY REVOKE YOUR PROXY AT ANY TIME PRIOR TO THE TIME IT IS
VOTED.
 
                                          By Order of the Board of Directors
                                          /s/ John M. Mendez
 
                                          John M. Mendez, Secretary
   3
 
                                PROXY STATEMENT
 
                         ANNUAL MEETING OF STOCKHOLDERS
                     TO BE HELD ON TUESDAY, APRIL 13, 1999
 
     The Board of Directors of First Community Bancshares, Inc. (The
"Corporation") solicits the enclosed proxy for use at the Annual Meeting of
Stockholders of First Community Bancshares, Inc., which will be held on Tuesday,
April 13, 1999, at 3:00 p.m., (local time) at Bluefield Elks Lodge, 1501
Whitethorn Street, Bluefield, West Virginia, and at any adjournment thereof.
 
     The expenses of the solicitation of the proxies for the meeting, including
the cost of preparing, assembling and mailing the notice, proxy statement and
return envelopes, the handling and tabulation of proxies received, and charges
of brokerage houses and other institutions, nominees or fiduciaries for
forwarding such documents to beneficial owners, will be paid by the Corporation.
In addition to the mailing of the proxy material, solicitation may be made in
person or by telephone or telegraph 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 19, 1999.
 
VOTING
 
     Shares of Common Stock (par value $1 per share) represented by proxies in
the accompanying form which are properly executed and returned to the
Corporation will be voted at the Annual Meeting in accordance with the
stockholder's instructions contained therein. In the absence of contrary
instructions, shares represented by such proxies will be voted FOR the election
of the nominees as described herein under "Election of Directors" and FOR
ratification of the selection of Deloitte & Touche as independent public
accountants for the year ended December 31, 1999. Any stockholder has the power
to revoke his proxy at any time before it is voted.
 
     The Board of Directors has fixed March 1, 1999 as the record date for
stockholders entitled to notice of and to vote at the Annual Meeting. Shares of
Common Stock outstanding on the record date are entitled to be voted at the
Annual Meeting and the holders of record will have one vote for each share so
held in the matters to be voted upon by the stockholders. There are no
cumulative voting rights.
 
     Directors are elected by a plurality of votes present in person or by proxy
and entitled to vote, assuming a quorum is present. All other matters coming
before the meeting will be determined by majority vote of those present in
person or by proxy and entitled to vote. Abstentions and broker non-votes for
shares represented at the meeting thus have no direct effect on the election of
directors but have the effect of negative votes on other matters to be
considered.
 
     As of the close of business on March 1, 1999, the outstanding shares of the
Corporation consisted of 7,043,961 shares of Common Stock.
 
                                        2
   4
 
                             ELECTION OF DIRECTORS
 
     The Corporation's Board of Directors is comprised of eleven directors,
including nine non-employee directors, divided into three classes with staggered
terms. All directors are elected for three-year terms.
 
     The nominees for the Board of Directors to serve until the Annual Meeting
of Stockholders in 2002 are set forth below. All nominees are currently serving
on the Corporation's Board of Directors. In the event any nominee is unable or
declines to serve as a director at the time of the Annual Meeting, the proxies
will be voted for any nominee who shall be designated by the present Board of
Directors to fill the vacancy. In the event that additional persons are
nominated for election as directors, the proxy holders intend to vote all
proxies received by them for the nominees listed below. All nominees named
herein have consented to be named and to serve as directors if elected.
 


                                        Principal Occupation and           Director of     Class
                                      Employment Last Five Years;          Corporation       of
Name                      Age           Principal Directorships               Since       Director
- --------------------------------------------------------------------------------------------------
                                                                              
Sam Clark                 67     Agent, State Farm Insurance; Director,       1993          2002
                                 First Community Bank, Inc. & First
                                 Community Bank of Mercer County, Inc.

Robert E. Perkinson, Jr.  51     Vice President-Operations, MAPCO Coal,       1994          2002
                                 Inc.; Permac, Inc.; Race Fork Coal
                                 Company; South Atlantic Coal, Inc.;
                                 Director, Virginia Coal Association;
                                 Director, First Community Bank, Inc. &
                                 First Community Bank of Mercer County,
                                 Inc.

William P. Stafford       65     President, Princeton Machinery               1989          2002
                                 Service, Inc.; Chairman of the Board
                                 of the Corporation; Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.

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

 
                                        3
   5
 
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 term. The name, age, principal occupation and certain
biographical information for each continuing director is presented below:
 


                                         Principal Occupation and            Director of    Class
                                       Employment Last Five Years;           Corporation      of
Name                      Age            Principal Directorships                Since      Director
- ---------------------------------------------------------------------------------------------------
                                                                               
Allen T. Hamner           57     Professor of Chemistry, West Virginia          1993         2001
                                 Wesleyan College; Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.

James L. Harrison, Sr.    51     President & Chief Executive Officer of         1989         2000
                                 the Corporation; President & Director of
                                 First Community Bank, Inc., First
                                 Community Bank of Mercer County, Inc. &
                                 First Community Bank of Southwest
                                 Virginia, Inc.; Executive Vice President
                                 & Director, Blue Ridge Bank

B. W. Harvey              67     President, Highlands Real Estate               1989         2001
                                 Management, Inc.; Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.

I. Norris Kantor          69     Partner, Katz, Kantor & Perkins,               1989         2000
                                 Attorneys-at-Law; Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.

John M. Mendez            44     Vice President & Chief Financial Officer       1994         2001
                                 of the Corporation;
                                 Vice-President -- Finance & Chief
                                 Administrative Officer & Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.; Director &
                                 Secretary, First Community Bank of
                                 Southwest Virginia, Inc.; Director and
                                 Assistant Corporate Secretary, Blue
                                 Ridge Bank

A. A. Modena              70     Past Executive Vice President and              1989         2000
                                 Secretary of the Corporation (Retired
                                 October 1, 1994); Director, First
                                 Community Bank, Inc. & First Community
                                 Bank of Mercer County, Inc.

William P. Stafford, II   35     Attorney, Brewster, Morhous & Cameron;         1994         2000
                                 Director, First Community Bank, Inc. &
                                 First Community Bank of Mercer County,
                                 Inc.

 
COMPENSATION OF DIRECTORS
 
     During 1998, non-employee members of the Board of Directors received a
director's fee of $500 per month. Directors of the Corporation may also be
reimbursed for travel or other expenses incurred in attendance at Board or
committee meetings. Directors who are employees of the Corporation receive no
additional compensation for service on the Board or its committees.
 
                                        4
   6
 
MEETING ATTENDANCE
 
     The Board of Directors held 13 meetings during 1998. All directors and
those nominees who are currently directors attended at least 75% of all meetings
of the Board and any committee of which they were a member.
 
BOARD COMMITTEES
 
     The Board of Directors of the Corporation has an Audit Committee consisting
of Chairman Stafford and Mr. Tinder, both non-employee members of the Board. The
Audit Committee of the Board of Directors, which held two meetings during 1998,
reviews and acts on reports to the Board with respect to various auditing and
accounting matters, the scope of the audit procedures and the results thereof,
the internal accounting and control systems of the Corporation, the nature of
service performed for the Corporation by and the fees to be paid to the
independent auditors, the performance of the Corporation's independent and
internal auditors and the accounting practices of the Corporation. The Audit
Committee also recommends to the full Board of Directors the auditors to be
appointed by the Board (subject to stockholders' ratification). The Board does
not maintain Nominating or Compensation Committees.
 
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 banks, and have had and expect to have transactions
with the banks. In addition, some of the directors and officers of the
Corporation are, as in the past, also officers of or partners in entities which
are customers of the banks and which have had and expect to have transactions
with the banks. 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.
 
REPORTS OF CHANGES IN BENEFICIAL OWNERSHIP
 
     Directors, executive officers and principal shareholders of the Corporation
are required to file Initial Statements of Beneficial Ownership and Changes in
Beneficial Ownership of holdings in the Corporation's stock. These filings on
Form 3, Form 4 and Form 5 are to be filed with the Securities and Exchange
Commission within various time frames following a change in status or changes in
the level of beneficial ownership. During 1998, a filing pursuant to these
requirements was inadvertently made on a late basis by Director Kantor.
 
                                        5
   7
 
PRINCIPAL STOCKHOLDERS
 
     The following sets forth information with respect to those persons, who to
the knowledge of management, beneficially owned more than 5% of the
Corporation's outstanding stock as of March 1, 1999. All shares are subject to
the named entity's sole voting and investment power.
 


Title of                                                        Shares Beneficially    Percent
 Class             Name and Address of Beneficial Owner                Owned           of Class
- -----------------------------------------------------------------------------------------------
                                                                              
Common        The H. P. & Anne S. Hunnicutt Foundation (1)            808,000           11.47%

Common        The First Community Bancshares, Inc.                    360,941            5.12%
              Employee Stock Ownership and Savings Plan

 
- ---------------
(1) William P. Stafford is deemed a beneficial owner of the same shares by
    virtue of his position as President of the Foundation.
 
OWNERSHIP OF COMMON STOCK BY DIRECTORS AND EXECUTIVE OFFICERS
 
     The following table sets forth the beneficial ownership of the Common Stock
of the Corporation as of March 1, 1999, by each director and nominee, each
executive officer named in the Summary Compensation Table, and all directors and
executive officers as a group including each executive officer named in this
Proxy Statement.
 


                                                            Percent of Class
Name of Group                          Number of Shares    Beneficially Owned
- -----------------------------------------------------------------------------
                                                     
Robert L. Buzzo                              6,018                 *
Sam Clark                                   40,556                 *
Allen T. Hamner                              2,886                 *
James L. Harrison, Sr.                      50,770                 *
B. W. Harvey                                 7,356                 *
I. Norris Kantor                            16,981                 *
John M. Mendez                              16,608                 *
A. A. Modena                                25,886                 *
Robert E. Perkinson, Jr. (1)                18,098                 *
William P. Stafford (2)                    157,507               2.24%
William P. Stafford, II                    121,183               1.72%
W. W. Tinder, Jr.                           45,750                 *
All Directors and Executive Officers       509,599               7.23%
  as a group (Twelve Persons)

 
- ---------------
(1) Mr. Perkinson serves as Co-trustee of the Trust Under Agreement for Robert
    E. Perkinson, Sr., and by virtue of voting power is deemed to share
    beneficial ownership of an additional 136,304 shares or 1.94% of the
    Corporation's outstanding stock held by the Trust.
 
(2) Mr. Stafford serves as President of The H. P. and Anne S. Hunnicutt
    Foundation, and by virtue of voting power is deemed to share beneficial
    ownership of an additional 808,000 shares or 11.47% of the Corporation's
    outstanding stock held by the Foundation.
 
 *  Less than one percent.
 
                                        6
   8
 
                        REPORT ON EXECUTIVE COMPENSATION
 
EXECUTIVE COMPENSATION POLICY
 
     Executive officers of the Corporation are not compensated by the
Corporation, but rather, by a wholly-owned subsidiary bank. Accordingly,
compensation of the executive officers who qualify for disclosure is determined
by the subsidiary bank's Executive Committee (executive management in the case
of Mr. Mendez and Mr. Buzzo), consisting of Bank Directors Bailey, Harvey,
Perkinson, W. P. Stafford, and Tinder. Although a member of the Executive
Committee, Mr. Harrison does not participate in any Committee discussions
related to his base, salary, bonus or incentives. Executive compensation
(including compensation of the Chief Executive Officer), as determined by the
Executive Committee ("Committee"), is not tied directly to Company performance
through specific criteria. The compensation policy of the Committee is to
provide competitive levels of compensation with appropriate recognition of
responsibility of the respective officers. Management compensation is intended
to be set at levels that the Committee believes to be consistent with other
companies in the banking industry of similar size, operations and performance.
 

                                  
               Dr. James P. Bailey   Robert E. Perkinson, Jr.
               B. W. Harvey          William P. Stafford
                                     W. W. Tinder, Jr.

 
EXECUTIVE COMPENSATION FOR THE YEARS ENDED DECEMBER 31, 1998, 1997 AND 1996
 
     The following summary compensation table sets forth the information
concerning compensation for services in all capacities awarded to, earned by or
paid to the Corporation's President and Chief Executive Officer, and to other
executive officers of the Corporation whose salary and bonus exceeded $100,000
during the years ended December 31, 1998, 1997 and 1996.
 
                           SUMMARY COMPENSATION TABLE
 


                            Capacities in Which                                     Other Annual
Name of Individual                 Served             Year    Salary     Bonus    Compensation (2)
- --------------------------------------------------------------------------------------------------
                                                                   
James L. Harrison, Sr.  President, Chief Executive    1998   $199,619   $    --       $46,609
                        Officer & Director of the     1997    193,687        --        56,274
                        Corporation; President &      1996    193,821        --        43,235
                        Director of First Community
                        Bank, Inc., First Community
                        Bank of Mercer County, Inc.
                        & First Community Bank of
                        Southwest Virginia, Inc.;
                        Executive Vice President and
                        Director, Blue Ridge Bank

 
                                        7
   9
 


                            Capacities in Which                                     Other Annual
Name of Individual                Served             Year    Salary     Bonus    Compensation (2)
- --------------------------------------------------------------------------------------------------
                                                                   
John M. Mendez          Vice President & Chief        1998   $154,970   $14,969       $ 8,062
                        Financial Officer of the      1997    144,608    22,910         6,153
                        Corporation; Vice             1996    135,307    14,295        10,413
                        President -- Finance, Chief
                        Administrative Officer &
                        Director of First Community
                        Bank, Inc., First Community
                        Bank of Mercer County, Inc.;
                        Director & Secretary, First
                        Community Bank of Southwest
                        Virginia, Inc.; Director and
                        Assistant Corporate
                        Secretary, Blue Ridge Bank

Robert L. Buzzo         Vice President of the         1998   $ 81,977   $ 3,154       $21,499
                        Corporation; Chief Executive  1997     80,402    26,396        13,943
                        Officer of the Bluefield      1996     76,881     7,668        11,267
                        Division of First Community
                        Bank of Mercer County, Inc.;
                        Director of First Community
                        Bank, Inc. & First Community
                        Bank of Mercer County, Inc.

 
- ---------------
(1) No long-term compensation is paid to the named executive officers.
 
(2) Other annual compensation includes non-qualified deferred compensation
    agreements, deferred bonuses and non-cash fringe benefits.
 
COMPARATIVE PERFORMANCE OF THE COMPANY
 
     The following chart compares cumulative total shareholder return on the
Corporation's Common Stock for the five-year period ended December 31, 1998 with
cumulative total shareholder return of: 1) The Standard & Poor's 500 market
index ("S&P 500"); 2) a group of three Peer Bank Holding Companies ("Peer A"),
selected by management of the Corporation based upon relative asset size and
geographic location; and 3) a group of six Peer Bank Holding Companies ("Peer
B") which was selected to replace the original peer group which has been
diminished in number due to mergers and acquisitions. Each of the three Banking
Holding Companies in Peer A are also included in Peer B. Both peer groups are
presented in this transition year. Subsequent years will present only Peer B,
the newly constituted, larger peer group.
 
                                        8
   10
 


                                               FCBC              S&P 500 Index           PEER Group A           PEER Group B
                                               ----              -------------           ------------           ------------
                                                                                                     
1993                                          100.00                 100.00                 100.00                 100.00
1994                                          134.00                 101.00                  92.00                  98.00
1995                                          149.00                 139.00                 116.00                 114.00
1996                                          162.00                 170.00                 134.00                 155.00
1997                                          241.00                 223.00                 201.00                 223.00
1998                                          240.00                 283.00                 200.00                 218.00

 
     The graph assumes an initial investment of $100 on December 31, 1993 in the
Corporation's common stock and each of the comparative investments with
dividends from each of the investments reinvested at year-end in additional
shares of the stock at the then current market value.
 
EMPLOYMENT CONTRACTS
 
     Under the provisions of employment contracts with Messrs. Harrison and
Mendez, in the event of a change in control of the Corporation, Harrison and
Mendez may elect to terminate services and be compensated at their annual salary
for the balance of the term of the contract or for a period of twelve months,
whichever is greater. In the event either officer is dismissed for reasons other
than cause, as defined, he will be compensated at his annual salary for the
balance of the term of the three-year contract, or twelve months, whichever is
greater.
 
EMPLOYEE STOCK OWNERSHIP PLAN
 
     The individuals listed in the Summary Compensation Table are covered under
an Employee Stock Ownership and Savings Plan ("ESOP"). Contributions under the
ESOP feature are made annually at the discretion of the Board of Directors.
Allocations of those contributions to participants' accounts are made on the
basis of relative W-2 compensation (up to $160,000). Allocations to the accounts
of the individuals named in the Summary Compensation table for the 1998 year
were: Harrison -- $16,000; Mendez -- $16,000; and Buzzo -- $10,663.
 
SAVINGS PLAN
 
     The Plan also provides a 401(k) Savings feature and matches employee
contributions at the rate of 25% up to 6% of compensation. Matching
contributions for 1998 for the covered persons listed in the Summary
Compensation table were as follows: Harrison -- $2,059; Mendez -- $1,767; and
Buzzo -- $931.
 
WRAP PLAN
 
     The Corporation maintains a Supplemental Executive Retirement Plan ("Plan")
for the purpose of providing deferred compensation which cannot be accumulated
under the Basic Plan provisions above
                                        9
   11
 
because of deferral and covered compensation limitations on tax-qualified
pension plan benefits. The Company makes a non-qualified matching credit on
employee contributions at the rate of 25% up to 6% of compensation under the
401(k) feature of the basic plan and also makes contributions in lieu of basic
plan ESOP contributions for compensation in excess of the $160,000 compensation
limit. Contributions under this Plan in 1998 for the covered persons listed in
the Summary Compensation Table were as follows: Harrison -- $9,634;
Mendez -- $2,144; and Buzzo -- $503.
 
                   RATIFICATION OF THE SELECTION OF AUDITORS
 
     Pursuant to the Bylaws of the Corporation, stockholders will be asked to
ratify the selection of Deloitte & Touche, Pittsburgh, Pennsylvania, as
independent auditors of the Corporation and its subsidiaries for the fiscal year
ending December 31, 1999. The firm of Deloitte & Touche as independent auditors
has examined the financial statements of the Corporation and its subsidiaries
each year since 1985 and has no relationship with the Corporation or its
subsidiaries except in its capacity as auditors. In connection with its audit of
the Corporation's financial statements for the years ended December 31, 1985
through 1998, Deloitte & Touche reviewed the Corporation's annual reports to
stockholders and its filings with the Securities and Exchange Commission and
conducted reviews of quarterly reports to stockholders.
 
     The Audit Committee of the Board of Directors has recommended to the Board
of Directors that Deloitte & Touche be appointed as independent auditors for the
year ended December 31, 1999. The Board of Directors has made that appointment
and recommends that the stockholders ratify the selection of Deloitte & Touche
as independent auditors for the ensuing year.
 
     A representative of Deloitte & Touche is not expected to be present at the
meeting. However, inquiries or questions of Deloitte & Touche may be directed to
Mr. Kenneth A. Liss, Partner, Deloitte & Touche, 2500 One PPG Place, Pittsburgh,
PA 15222-5401, (412) 338-7200.
 
                                 OTHER MATTERS
 
     All properly executed proxies received by the Corporation will be voted at
the meeting in accordance with the specifications contained thereon. The Board
of Directors knows of no other matter which may properly come before the meeting
for action. However, if any other matter does properly come before the meeting,
the persons named in the proxy materials enclosed will vote in accordance with
their judgment upon such matter.
 
                                       10
   12
 
                             STOCKHOLDER PROPOSALS
 
     If any stockholder intends to present a proposal at the 2000 Annual
Meeting, such proposals must be received by the Corporation at its principal
executive offices on or before November 18, 1999. Otherwise, such proposal will
not be considered for inclusion in the Corporation's Proxy Statement for such
meeting.
 
     You are urged to properly complete, execute and return the enclosed form of
proxy.
 
                                          By Order of the Board of Directors
                                          /s/ John M. Mendez
 
                                          John M. Mendez, Secretary to the Board
                                          March 17, 1999
 
                                       11
   13

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 
AND 2 ABOVE.

Dated: _______________________, 1999           ________________________________
                                                   Signature of Stockholder

                                               ________________________________
                                                   Signature of Stockholder

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

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


                    PROXY FOR ANNUAL MEETING OF STOCKHOLDERS
             First Community Bancshares, Inc. o 1001 Mercer Street,
                         Princeton, West Virginia 24740

          THIS PROXY IS SOLICITED ON BEHALF OF THE BOARD OF DIRECTORS

The undersigned hereby constitutes and appoints Robert L. Schumacher and Barbara
J. Buchanan, or either of them attorney and proxy with full power of
substitution, to be present the undersigned at the Annual Meeting of the
Stockholders of First Community Bancshares, Inc. (the "Corporation") to be held
on Tuesday, April 13, 1999, at the Bluefield Elks Lodge, 1501 Whitethorn Street,
Bluefield, West 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.


                                                               
FOR [ ]  the election of 4 directors - Class of 2002              WITHHOLD AUTHORITY
         Sam Clark                    William P. Stafford         You may withhold authority to vote for any nominee by lining
         Robert E. Perkinson, Jr.     W. W. Tinder, Jr.           through or otherwise striking out his name.



To ratify the selection of the firm Deloitte & Touche LLP, Pittsburgh, 
Pennsylvania, as independent auditors for the Corporation for the fiscal year 
ending December 31, 1999.

FOR [ ]       AGAINST [ ]     ABSTAIN [ ]

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

                              CONTINUED ON REVERSE