As filed with the Securities and Exchange Commission on November 10, 2004

Registration No. 333-          

SECURITIES AND EXCHANGE COMMISSION
WASHINGTON, D.C. 20549

FORM S-8

REGISTRATION STATEMENT
UNDER
THE SECURITIES ACT OF 1933

FIRST COMMUNITY BANCSHARES, INC.

One Community Place
Bluefield, Virginia 24605
(Address of Principal Executive Offices, Including Zip Code)

FIRST COMMUNITY BANCSHARES, INC.
2004 OMNIBUS STOCK OPTION PLAN
(Full Titles of the Plans)

John M. Mendez
President and Chief Executive Officer
First Community Bancshares, Inc.
One Community Place
Bluefield, Virginia 24605
(Name and Address of Agent for Service)

(276) 326-9000
(Telephone Number, Including Area Code, of Agent for Service)

Copy to:

Norman B. Antin, Esq.
Jeffrey D. Haas, Esq.
Patton Boggs LLP
2550 M Street, NW
Washington, DC 20037
(202) 457-6000

CALCULATION OF REGISTRATION FEE

PART I

INFORMATION REQUIRED IN THE SECTION 10(a) PROSPECTUS

     The documents containing the information specified in Part I will be sent or given to employees as specified by Rule 428(b)(1) of the Securities Act of 1933, as amended (the “Securities Act”). Such documents are not being filed with the Securities and Exchange Commission (the “Commission”) either as part of this Registration Statement or as prospectuses or prospectus supplements pursuant to Rule 424 of the Securities Act. Such documents and the documents incorporated by reference in this Registration Statement pursuant to Item 3 of Part II hereof, taken together, constitute a prospectus that meets the requirements of Section 10(a) of the Securities Act.

     Employees participating in the 2004 Omnibus Stock Option Plan (the “Plan”) may obtain a copy of the Plan or the documents incorporated by reference in Item 3 of Part II below, at no cost, by writing or telephoning First Community Bancshares, Inc. (the “Registrant”) at: One Community Place, Bluefield, Virginia 24605, (276) 326-9000, Attention: Corporate Secretary. These documents are also incorporated by reference in the prospectus.

PART II

INFORMATION REQUIRED IN THE REGISTRATION STATEMENT

Item 3. Incorporation of Documents by Reference.

     The following documents filed with the Commission by the Registrant are hereby incorporated by reference in this Registration Statement:

     (a) Annual Report on Form 10-K for the year ended December 31, 2003, filed on March 15, 2004 and as amended on May 19, 2004.

     (b) All other reports filed by the Registrant pursuant to Sections 13(a) or 15(d) of the Securities Exchange Act of 1934, as amended (the “Exchange Act”), since the end of the fiscal year covered by the Form 10-K referred to in clause (a) above.

     (c) The description of the Registrant’s common stock contained in the Registrant’s Form 8-A, as filed with the Commission pursuant to Sections 12(b) and 12(g) of the Exchange Act, on May 20, 1991.

     All documents filed by the Registrant pursuant to Sections 13(a), 13(c), 14 or 15(d) of the Exchange Act, after the date hereof and prior to the filing of a post-effective amendment to this Registration Statement indicating that all securities offered hereby have been sold or which deregisters all such securities then remaining unsold, shall also be deemed to be incorporated by reference in this Registration Statement and to be a part hereof commencing on the respective dates on which such reports and documents are filed with the Commission. Any statement incorporated by reference herein shall also be deemed to be modified or superseded for the purposes of this Registration Statement and any amendment or supplement hereto to the

2

extent that a statement contained herein or in any other subsequently filed document which also is or is deemed to be incorporated by reference herein modifies or supersedes such statement. Any statement modified or superseded shall not be deemed, except as so modified or superseded, to constitute part of this Registration Statement or any such amendment or supplement.

Item 4. Description of Securities.

     Not applicable.

Item 5. Interests of Named Experts and Counsel.

     Not applicable.

Item 6. Indemnification of Directors and Officers.

Article Eighth of the Registrant’s Articles of Incorporation provides:

(a) The corporation shall indemnify any person who was or is a party or is threatened to be made a party to any threatened, pending or completed action, suit or proceeding, whether civil, criminal, administrative or investigative (other than an action by or in the right of the corporation) by reason of the fact that he is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise, against expenses (including attorneys’ fees), judgments, fines and amounts paid in settlement actually and reasonably incurred by him in connection with such action, suit or proceeding if he acted in good faith and in a manner he reasonably believed to be in or not opposed to be the best interests of the corporation, and, with respect to any criminal action or proceeding, had no reasonable cause to believe his conduct was unlawful.

(b) The corporation shall indemnify any person who was or is a party or is threatened to be made a party to any threatened, pending or completed action or suit by or in the right of the corporation to procure a judgment in its favor by reason of the fact that he is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise against expenses (including amounts paid in settlement and attorneys’ fees) actually and reasonably incurred by him in connection with the defense or settlement of such action or suit if he acted in good faith and in a manner he reasonably believed to be in or not opposed to the best interests of the corporation, except that no indemnification shall be made in respect of any claim, issue or matter as to which such person shall have been finally adjudged to be liable to the corporation unless and only to the extent that an appropriate court shall determine upon application that, despite the adjudication of liability but in view of all the circumstances of the case, such person is fairly and reasonably entitled to indemnify for such expenses as the court shall deem proper.

(c) Any indemnification under subsections (a) and (b) of this Article (unless ordered by the court) shall be made by the corporation only as authorized in the specific case upon a

3

determination that indemnification of the director, officer, employee or agent is proper in the circumstances because he has met the applicable standard of conduct set forth in subsections (a) and (b) of this Article. Such determination shall be made (1) by the Board of Directors by a majority vote of a quorum constituting of directors who were not parties to such action, suit or proceeding, or (2) if such a quorum is not obtainable, or, even if obtainable a quorum of disinterested Directors so directs, by independent legal counsel in a written opinion, or (3) by the stockholders.

(d) Expenses incurred by an officer or director in defending a civil or criminal action, suit or proceeding shall be paid by the corporation as incurred and in advance of the final disposition of such action, suit or proceeding upon receipt of an undertaking by or on behalf of such director or officer to repay such amount if it shall ultimately be determined by a court of competent jurisdiction that he is not entitled to be indemnified by the corporation as authorized in this section. Such expense incurred by other employees and agents may be so paid upon such terms and conditions, if any, as the Board of Directors deems appropriate.

(e) The corporation may (but need not) purchase and maintain insurance on behalf of any person who is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise against any liability asserted against him or expenses incurred by him in any such capacity, or arising out of this status as such, whether or not the corporation would have the power to indemnify him against such liability under this section.

(f) No director of the corporation shall be liable to the corporation or its stockholders for monetary damages for breach of fiduciary duty as a director, provided that such provision shall not eliminate or limit the liability of a director; (i) for any breach of the director’s duty of loyalty to the corporation or its stockholders; (ii) for acts or omissions which involve intentional misconduct, fraud or a knowing violation of law; (iii) for the payment of any distribution in violation of Nevada Revised Statute 78.300; or (iv) for any transaction from which the director derived an improper personal benefit.

The Nevada General Corporation Law provides as follows:

78.7502 DISCRETIONARY AND MANDATORY INDEMNIFICATION OF OFFICERS, DIRECTORS, EMPLOYEES AND AGENTS: GENERAL PROVISIONS.

1. A corporation may indemnify any person who was or is a party or is threatened to be made a party to any threatened, pending or completed action, suit or proceeding, whether civil, criminal, administrative or investigative, except an action by or in the right of the corporation, by reason of the fact that he is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise, against expenses, including attorneys’ fees, judgments, fines and amounts paid in settlement actually and reasonably incurred by him in connection with the action, suit or proceeding if he:

4

(a) Is not liable pursuant to NRS 78.138; or

(b) Acted in good faith and in a manner which he reasonably believed to be in or not opposed to the best interests of the corporation, and, with respect to any criminal action or proceeding, had no reasonable cause to believe his conduct was unlawful.

The termination of any action, suit or proceeding by judgment, order, settlement, conviction or upon a plea of nolo contendere or its equivalent, does not, of itself, create a presumption that the person is liable pursuant to NRS 78.138 or did not act in good faith and in a manner which he reasonably believed to be in or not opposed to the best interests of the corporation, or that, with respect to any criminal action or proceeding, he had reasonable cause to believe that his conduct was unlawful.

2. A corporation may indemnify any person who was or is a party or is threatened to be made a party to any threatened, pending or completed action or suit by or in the right of the corporation to procure a judgment in its favor by reason of the fact that he is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise against expenses, including amounts paid in settlement and attorneys’ fees actually and reasonably incurred by him in connection with the defense or settlement of the action or suit if he:

(a) Is not liable pursuant to NRS 78.138; or

(b) Acted in good faith and in a manner which he reasonably believed to be in or not opposed to the best interests of the corporation.

Indemnification may not be made for any claim, issue or matter as to which such a person has been adjudged by a court of competent jurisdiction, after exhaustion of all appeals therefrom, to be liable to the corporation or for amounts paid in settlement to the corporation, unless and only to the extent that the court in which the action or suit was brought or other court of competent jurisdiction determines upon application that in view of all the circumstances of the case, the person is fairly and reasonably entitled to indemnity for such expenses as the court deems proper.

3. To the extent that a director, officer, employee or agent of a corporation has been successful on the merits or otherwise in defense of any action, suit or proceeding referred to in subsections 1 and 2, or in defense of any claim, issue or matter therein, the corporation shall indemnify him against expenses, including attorneys’ fees, actually and reasonably incurred by him in connection with the defense.

78.751 AUTHORIZATION REQUIRED FOR DISCRETIONARY INDEMNIFICATION; ADVANCEMENT OF EXPENSES; LIMITATION ON INDEMNIFICATION AND ADVANCEMENT OF EXPENSES.

1. Any discretionary indemnification pursuant to NRS 78.7502, unless ordered by a court or advanced pursuant to subsection 2, may be made by the corporation only as authorized in the

5

specific case upon a determination that indemnification of the director, officer, employee or agent is proper in the circumstances. The determination must be made:

(a) By the stockholders;

(b) By the board of directors by majority vote of a quorum consisting of directors who were not parties to the action, suit or proceeding;

(c) If a majority vote of a quorum consisting of directors who were not parties to the action, suit or proceeding so orders, by independent legal counsel in a written opinion; or

(d) If a quorum consisting of directors who were not parties to the action, suit or proceeding cannot be obtained, by independent legal counsel in a written opinion.

2. The articles or incorporation, the bylaws or an agreement made by the corporation may provide that the expenses of officers and directors incurred in defending a civil or criminal action, suit or proceeding must be paid by the corporation as they are incurred and in advance of the final disposition of the action, suit or proceeding, upon receipt of an undertaking by or on behalf of the director or officer to repay the amount if it is ultimately determined by a court of competent jurisdiction that he is not entitled to be indemnified by the corporation. The provisions of this subsection do not affect any rights to advancement of expenses to which corporate personnel other than directors or officers may be entitled under any contract or otherwise by law.

3. The indemnification pursuant to NRS 78.7502 and advancement of expenses authorized in or ordered by a court pursuant to this section:

(a) Does not exclude any other rights to which a person seeking indemnification or advancement of expenses may be entitled under the articles or incorporation or any bylaw, agreement, vote of stockholders or disinterested directors or otherwise, for either an action in his official capacity or an action in another capacity while holding his office, except that indemnification, unless ordered by a court pursuant to NRS 78.7502 or for the advancement of expenses made pursuant to subsection 2, may not be made to or on behalf of any director or officer if a final adjudication establishes that his acts or omissions involved intentional misconduct, fraud or a knowing violation of the law and was material to the cause of action.

(b) Continues for a person who has ceased to be a director, officer, employee or agent and inures to the benefit of the heirs, executors and administrators of such a person.

78.752 INSURANCE AND OTHER FINANCIAL ARRANGEMENTS AGAINST LIABILITY OF DIRECTORS, OFFICERS, EMPLOYEES AND AGENTS.

1. A corporation may purchase and maintain insurance or make other financial arrangements on behalf of any person who is or was a director, officer, employee or agent of the corporation, or is or was serving at the request of the corporation as a director, officer, employee

6

or agent of another corporation, partnership, joint venture, trust or other enterprise for any liability asserted against him and liability and expenses incurred by him in his capacity as a director, officer, employee or agent, or arising out of his status as such, whether or not the corporation has the authority to indemnify him against such liability and expenses.

2. The other financial arrangements made by the corporation pursuant to subsection 1 may include the following:

(a) The creation of a trust fund.

(b) The establishment of a program of self-insurance.

(c) The securing of its obligation of indemnification by granting a security interest or other lien on any assets of the corporation.

(d) The establishment of a letter of credit, guaranty or surety.

No financial arrangement made pursuant to this subsection may provide protection for a person adjudged by a court of competent jurisdiction, after exhaustion of all appeals therefrom, to be liable for intentional misconduct, fraud or a knowing violation of law, except with respect to the advancement of expenses or indemnification ordered by a court.

3. Any insurance or other financial arrangement made on behalf of a person pursuant to this section may be provided by the corporation or any other person approved by the board of directors, even if all or part of the other person’s stock or other securities is owned by the corporation.

4. In the absence of fraud:

(a) The decision of the board of directors as to the propriety of the terms and conditions of any insurance or other financial arrangement made pursuant to this section and the choice of the person to provide the insurance or other financial arrangement is conclusive; and

(b) The insurance or other financial arrangement:

(1) Is not void or voidable; and

(2) Does not subject any director approving it to personal liability for his action, even if a director approving the insurance or other financial arrangement is a beneficiary of the insurance or other financial arrangement.

5. A corporation or its subsidiary which provides self-insurance for itself or for another affiliated corporation pursuant to this section is not subject to the provisions of Title 57 of NRS.

7

Item 7. Exemption from Registration Claimed.

     Not applicable.

Item 8. Exhibits.

Item 9. Undertakings.

     (a) The undersigned Registrant hereby undertakes:

        (1) To file, during any period in which offers or sales are being made, a post-effective amendment to this Registration Statement:

            (i) To include any prospectus required by Section 10(a)(3) of the Securities Act;

            (ii) To reflect in the prospectus any facts or events arising after the effective date of the registration statement (or the most recent post-effective amendment thereof) which, individually or in the aggregate, represent a fundamental change in the information set forth in the registration statement. Notwithstanding the foregoing, any increase or decrease in volume of securities offered (if the total dollar value of securities offered would not exceed that which was registered) and any deviation from the low or high and of the estimated maximum offering range may be reflected in the form of prospectus filed with the Commission pursuant to Rule 424(b) if, in the aggregate, the changes in volume and price represent no more than a 20 percent change in the maximum aggregate offering price set forth in the “Calculations of Registration Fee” table in the effective registration statement.

8

            (iii) To include any material information with respect to the plan of distribution not previously disclosed in the registration statement or any material change to such information in the registration statement;

provided, however, that paragraphs (1)(i) and (1)(ii) do not apply if the registration statement is on Form S-3, Form S-8 or Form F-3, and the information required to be included in a post-effective amendment by those paragraphs is contained in periodic reports filed with or furnished to the Commission by the Registrant pursuant to Section 13 or Section 15(d) of the Exchange Act that are incorporated by reference in the registration statement.

        (2) That, for the purpose of determining any liability under the Securities Act, each such post-effective amendment shall be deemed to be a new registration statement relating to the securities offered therein, and the offering of such securities at that time shall be deemed to be the initial bona fide offering thereof.

        (3) To remove from registration by means of a post-effective amendment any of the securities being registered which remain unsold at the termination of the offering.

     (b) The undersigned Registrant hereby undertakes that, for purposes of determining any liability under the Securities Act of 1933, each filing of the Registrant’s annual report pursuant to Section 13(a) or 15(d) of the Securities Exchange Act of 1934 (and, where applicable, each filing of an employee benefit plan’s annual report pursuant to Section 15(d) of the Securities Exchange Act of 1934) that is incorporated by reference in the Registration Statement shall be deemed to be a new registration statement relating to the securities offered therein, and the offering of such securities at that time shall be deemed to be the initial bona fide offering thereof.

     (c) Insofar as indemnification for liabilities arising under the Securities Act of 1933 may be permitted to directors, officers and controlling persons of the Registrant pursuant to the foregoing provisions, or otherwise, the Registrant has been advised that in the opinion of the Securities and Exchange Commission such indemnification is against public policy as expressed in the Securities Act of 1933, as amended, and is, therefore, unenforceable. In the event that a claim for indemnification against such liabilities (other than the payment by the Registrant of expenses incurred or paid by a director, officer or controlling person of the Registrant in the successful defense of any action, suit or proceeding) is asserted by such director, officer or controlling person in connection with the securities being registered, the Registrant will, unless in the opinion of its counsel the matter has been settled by controlling precedent, submit to a court of appropriate jurisdiction the question whether such indemnification by it is against public policy as expressed in the Securities Act of 1933, as amended, and will be governed by the final adjudication of such issue.

9

SIGNATURES

     Pursuant to the requirements of the Securities Act, the Registrant certifies that it has reasonable grounds to believe that it meets all of the requirements for filing on Form S-8 and has duly caused this Registration Statement to be signed on its behalf by the undersigned, thereunto duly authorized, in the Commonwealth of Virginia, on November 10_, 2004.

10

POWER OF ATTORNEY

     Pursuant to the requirements of the Securities Act, this Registration Statement has been signed by the following persons in the capacities and on the date indicated. Each person whose signature appears below, hereby makes, constitutes and appoints John M. Mendez and Robert L. Schumacher, and each of them severally, as his or her attorney-in-fact to sign for such person and in such person’s name and capacity indicated below, and with full power of substitution, any and all amendments to this Registration Statement and any subsequent Registration Statement filed pursuant to Rule 462 under the Securities Act, hereby ratifying and confirming such person’s signature as it may be signed by said attorney to any and all amendments.

11

EXHIBIT INDEX