First Community Bancshares, Inc.
One Community Place
Bluefield, Virginia 24605-0989

Table of Contents

Notice of 2005
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 26, 2005, for the purpose of considering and voting upon the following items as more fully discussed herein.

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

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 3:00 a.m. eastern daylight time on April 26, 2005; 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 26, 2005

     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 26, 2005 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 22, 2005.

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 proposed amendment to the Articles of Incorporation and FOR ratification of the selection of Ernst & Young LLP as the independent Registered Public Accounting Firm for the year ended December 31, 2005.

     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 record holder to vote personally at the Annual Meeting.

     The Board of Directors has fixed March 8, 2005 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 amend the Articles of Incorporation requires the affirmative vote of the holders of a majority of the outstanding common stock entitled to vote. The proposal to ratify the appointment of the independent Registered Public Accounting Firm 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, the amendment to the Articles of Incorporation or the ratification of the independent Registered Public Accounting Firm. 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.

2

     As of the close of business on March 8, 2005, the outstanding shares of the Corporation consisted of 11,258,748 shares of Common Stock.

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 and Mr. William P. Stafford, II, who are deemed not independent due to their family relationship to a service provider to 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 2008 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.

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

3

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:

4

Executive Officers who are not Directors

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

Compensation of Directors

     During 2004, non-employee members of the Board of Directors received a retainer fee of $700 per month. During 2004, 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 2004. 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, 2004 by non-employee directors were 28,840 shares. The exercise price of each option is 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 twelve meetings during 2004. 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.

5

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. The Audit Committee of the Board of Directors, which operates under a Board approved charter, held fourteen meetings during 2004, 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 Registered Public Accounting Firm, the performance of the Corporation’s Independent Registered Public Accounting Firm and internal auditors and the accounting practices of the Corporation. In 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 Registered Public Accounting Firm, subject to stockholders’ ratification. The 2004 Report of the Audit Committee is presented on page 11 of this Proxy Statement.

Compensation Committee

     The Board of Directors assumed the duties of the former Compensation Committee on June 15, 2004. The independent members of the Board are responsible for the review and consideration of the form and amount of compensation and contractual employment terms of the President and Chief Executive Officer of the Corporation, the review of compensation of other executive officers and the review of stock-based compensation plans and various non-qualified compensation and retirement programs maintained by the Corporation. These compensation related responsibilities are now under the purview of the independent members of the Board of Directors. The 2004 Report of the Independent Members of the Board of Directors regarding compensation matters is presented on page 9 and 10 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 one meeting during 2004. 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 was attached as Appendix A to the Corporation’s 2004 Annual Meeting Proxy Statement, which was filed with the Securities and Exchange Commission on March 15, 2004.

     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,

6

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, the number of shares beneficially owned and the period they have been held.

     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:

     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 $46,007 for these professional services in 2004.

     In 2004, the Corporation constructed a bank facility in Princeton, WV at an estimated cost of approximately $1.8 million and the general contractor for this project was 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. During 2004, Fredeking Stafford Construction Company, Inc. received approximately $851,000 for its general contracting services rendered in regard to construction of this bank facility and provided other general contracting services to the Corporation during 2004, for which the Corporation paid $29,000. 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

7

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 2004, 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 Dr. Allen Hamner who filed a late Form 4 in connection with the purchase of 96 shares of common stock of the Corporation.

Beneficial Ownership of Common Stock by Certain Beneficial Owners and Management

     The following table sets forth as of March 8, 2005, 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.

8

Report on Executive Compensation

     The Independent Members of the Board of Directors establish and manage employment terms and the form and levels of compensation paid to the President and Chief Executive Officer (“CEO”). These Independent Members also periodically review 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 Independent Members of the Board 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 Independent Members of the Board 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

9

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 Independent Members of the Board utilized the Sheshunoff Executive Compensation Survey and the 2004 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 2004 fiscal year, the committee awarded a merit increase which resulted in a total increase in base compensation from $274,900 to $325,000 annually. This salary adjustment was effective January 1, 2004.

     In 2004 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 2004 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 2004 was $100,000.

     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.

Compensation Committee Interlocks and Insider Participation

     No independent member of the Board of Directors is an officer or employee of the Corporation and no such member or executive officer of the Corporation has a relationship that would constitute an interlocking relationship with executive officers or directors of another public company.

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, approved by the Corporation’s Board of Directors that complies with the Sarbanes-Oxley Act of 2002.

     The responsibilities of the Audit Committee include the appointment of an Independent Registered Public 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 and expressing an opinion on management’s assessment of

10

the effectiveness of the Corporation’s internal control over financial reporting. Additionally, and as appropriate, the Audit Committee reviews, evaluates, discusses, and consults with management, internal audit personnel and the Independent Registered Public Accounting Firm regarding the following:

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

     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 fourteen meetings during the fiscal year 2004 and took a number of steps in making the independent registered public accounting firm recommendation. First, the Audit Committee discussed with its Independent Registered Public Accounting Firm those matters the firm 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 Independent Registered Public Accounting firm’s independence with that firm and received a letter from the registered public accounting firm concerning independence as required under applicable independence standards for auditors of public companies. This discussion and disclosure informed the Audit Committee of the Independent Registered Public Accounting Firm’s independence, and assisted the Audit Committee in evaluating such independence. Finally, the Audit Committee reviewed and discussed, with the Corporation management and the Independent Registered Public Accounting Firm, the Corporation’s audited consolidated balance sheet at December 31, 2004 and consolidated statement of income, cash flows and stockholders’ equity for the year then ended. Based on discussions with the Independent Registered Public Accounting Firm 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 2004 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
Allen T. Hamner, Audit Committee Member
B. W. Harvey, Audit Committee Member

11

Executive Compensation for the Years Ended December 31, 2004, 2003 and 2002

     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, 2004.

12

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, 2004 represent the right to acquire an aggregate of 288,199 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 through January 1, 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, 2004, 42,836 options shares were outstanding and exercisable under the former CommonWealth Plan.

     There were no options granted to the Executive Officers in 2004.

13

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, 2004 and options held at December 31, 2004.

Option Exercises in Last Fiscal Year

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. The Corporation makes a non-qualified matching credit on employee contributions at the rate established in the 401(k) Plan (100% in 2004) of up to 6% of compensation deferred and also makes contributions in lieu of Qualified ESOP contributions for compensation in excess of the $205,000 compensation limit. Contributions under the Wrap Plan in 2004 for the covered persons are included in the Summary Compensation Table and are as follows: Mendez — $17,600; Buzzo — $3,941; Lilly — $6,375; and Schumacher — $3,123.

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

14

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.

     The vesting schedule under the plan provides 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.

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

     The Supplemental Retirement Plan was designed to retain the future services of Directors. Benefits become payable in a lump sum commencing 30 days following termination of service, except for cause, prior to retirement age as defined in the Plan document.

Indemnification Agreements

     The Corporation and its subsidiary bank have Indemnification Agreements for all Directors, executive officers Mendez, Buzzo, Lilly and Schumacher and certain other officers. The Indemnification Agreements indemnify each Director and officer to the fullest extent permitted by law. The Indemnification Agreements cover all expenses (including attorneys fees), judgments, fines and amounts paid in settlement, if such settlement is approved in advance by the Corporation, paid in

15

any matter relating to the Director’s or officer’s role as the Corporation’s director, officer, employee or agent when serving as its representative with respect to another entity. A Director or officer would not be entitled to indemnification in connection with a proceeding or claim initiated by such Director or officer voluntarily and that is not a defense.

16

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, 2004 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.

17

2 TO AMEND THE ARTICLES OF INCORPORATION TO INCREASE THE AUTHORIZED COMMON STOCK

     At the Annual Meeting, stockholders will be asked to consider and approve a proposal to amend the Company’s Articles of Incorporation, as amended (“Articles of Incorporation”) to increase the number of shares of authorized Common Stock from 15,000,000 to 25,000,000. The amendment to increase the number of authorized shares of Common Stock was unanimously approved by the Board of Directors of the Company on February 15, 2005.

     The Articles of Incorporation currently authorize 15,000,000 shares of capital stock, consisting of 15,000,000 shares of Common Stock. The proposed amendment to the Articles of Incorporation would increase the number of shares of authorized capital stock by 10,000,000, from 15,000,000 to 25,000,000 shares. If the amendment is authorized, the first sentence of Article FOURTH of the Company’s Articles of Incorporation would be amended to read as follows:

     “The total number of shares of capital stock which the Company has authority to issue is 25,000,000 shares of Common Stock, all of par value of One Dollar per share ($1.00) (hereinafter the “Common Stock”), and One Million (1,000,000) shares of preferred stock (hereinafter the “Preferred Stock”), whose par value, voting powers, designations, preferences, interest rate, limitations, restrictions and relative rights shall be determined from time to time by resolution of the Board of Directors of the Company.

     The Company is seeking stockholder approval to amend its Articles of Incorporation for several reasons. The Board of Directors has determined that the number of shares of authorized Common Stock should be increased to provide the Company with the flexibility to conduct the Company’s future operations, including the issuance, distribution, exchange or reservation of shares of Common Stock for stock dividends, acquisitions, financing and employee stock compensation plans. The Company has no present plans, arrangements or understandings with respect to a possible acquisition. The Board of Directors currently has no specific plans to issue additional Common Stock, except pursuant to the Company’s stock compensation plan.

     Under certain circumstances, authorized but unissued shares of Common Stock and Preferred Stock can provide the Board of Directors with a means of discouraging an unsolicited change in control of the Company. Although the proposed amendment may enable the Board of Directors to issue additional shares of Common Stock in the event of an unsolicited attempt to acquire control of the Company as a means of discouraging a hostile acquirer, the Board of Directors has no present intention of using the existing or proposed authorized but unissued Common Stock or the existing authorized but unissued Preferred Stock for such purpose. The Board of Directors is not presently aware of any plans to acquire control of the Company.

     If stockholders of the Company approve the proposed amendment to the Articles of Incorporation, the Company will file articles of amendment to the Articles of Incorporation of the Company with the Secretary of State of the State of Nevada reflecting the increase in authorized capitalization.

THE BOARD OF DIRECTORS OF THE COMPANY UNANIMOUSLY RECOMMENDS THAT STOCKHOLDERS OF THE COMPANY VOTE “FOR” APPROVAL OF ADOPTION OF THE PROPOSAL TO AMEND THE ARTICLES OF INCORPORATION TO INCREASE THE NUMBER OF AUTHORIZED SHARES OF COMMON STOCK.

18

3. RATIFICATION OF THE SELECTION OF INDEPENDENT REGISTERED PUBLIC
ACCOUNTING FIRM

     Stockholders are being asked to ratify the selection of Ernst & Young LLP, as the Independent Registered Public Accounting Firm of the Corporation and its subsidiaries for the fiscal year ending December 31, 2005. Ernst & Young served as the independent registered public accounting firm for the Corporation for the fiscal year ended December 31, 2004. Ernst & Young has no relationship with the Corporation or its subsidiaries except in its capacity as proposed Independent Registered Public Accounting Firm. In connection with its audit of the Corporation’s financial statements for the year ending December 31, 2005, 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 the Independent Registered Public Accounting Firm for the year ending December 31, 2005. The Board of Directors has made that appointment and recommends that the stockholders ratify the selection of Ernst & Young as Independent Registered Public Accounting Firm 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 REGISTERED PUBLIC ACCOUNTING FIRM FOR THE YEAR ENDING DECEMBER 31, 2005.

Audit Fees

     Fees for professional services provided by Ernst & Young LLP, the Corporation’s Independent Registered Public Accounting Firm, for the respective fiscal years ended December 31 are set forth below:

     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 as well as the audit of management’s assertion as to the effectiveness of internal control over financial reporting. 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 Registered Public Accounting Firm. 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-approved with respect to that year, the Audit Committee must approve the permitted service before the Independent Registered Public Accounting Firm is engaged to perform it. The Audit Committee has delegated to the Chair of the Audit

19

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, 2004 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 2004 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 2006 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 22, 2005. 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 2006 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 5, 2006.

     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.

20

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