EXHIBIT 10.9


                            HEARTLAND COMMUNITY BANK
                              HCB BANCSHARES, INC.

                                -----------------

                                Change-in-Control
                            Protective Agreement with
                                -----------------
                                -----------------


     THIS  AGREEMENT  entered into this 19th day of July,  2001,  by and between
HEARTLAND Community Bank (the "Bank"), HCB Bancshares, Inc. (the "Company"), and
Paula J. Bergstrom (the  "Employee"),  effective on the date of the execution of
this agreement (the "Effective Date").


     WHEREAS,  the  Employee  has  heretofore  been  employed  by the Bank as an
officer,  and the Company  and the Bank deem it to be in their best  interest to
enter into this Agreement as additional incentive to the Employee to continue as
an officer of the Bank; and


     WHEREAS,   the  parties   desire  by  this   writing  to  set  forth  their
understanding  as to their  respective  rights  and  obligations  in the event a
change of control occurs with respect to the Bank or the Company.


     NOW, THEREFORE, the undersigned parties AGREE as follows:


     1. Defined Terms


          When used anywhere in the  Agreement,  the following  terms shall have
the meaning set forth herein.


          (a) "Change in Control"  shall mean any one of the  following  events:
(i) the acquisition of ownership,  holding or power to vote more than 50% of the
Bank's or the Company's  voting stock,  (ii) the  acquisition  of the ability to
control the  election of a majority  of the Bank's or the  Company's  directors,
(iii) the acquisition of a controlling influence over the management or policies
of the Bank or the  Company  by any  person  or by  persons  acting as a "group"
(within the meaning of Section 13(d) of the Securities Exchange Act of 1934), or
(iv) during any period of two consecutive  years,  individuals  (the "Continuing
Directors")  who at the  beginning  of  such  period  constitute  the  Board  of
Directors of the Bank or the Company (the "Existing Board") cease for any reason
to constitute at least  two-thirds  thereof,  provided that any individual whose
election  or  nomination  for  election  as a member of the  Existing  Board was
approved by a vote of at least  two-thirds of the  Continuing  Directors then in
office shall be considered a Continuing Director. Notwithstanding the foregoing,
in the case of (i), (ii) and (iii)  hereof,  ownership or control of the Bank by
the Company  itself shall not  constitute  a Change in Control.  For purposes of
this paragraph only, the term "person" refers to an individual or a corporation,
partnership,   trust,   association,   joint  venture,  pool,  syndicate,   sole
proprietorship,  unincorporated  organization  or any other  form of entity  not
specifically listed herein. The decision of the Bank's non-employee directors as
to whether or not a Change in  Control  has  occurred  shall be  conclusive  and
binding.


          (b) "Code"  shall mean the Internal  Revenue Code of 1986,  as amended
from time to time, and as interpreted through applicable rulings and regulations
in effect from time to time.


                    (c) "Code Section 280G  Maximum"  shall mean product of 2.99
          and  the   Employee's   "base  amount"  as  defined  in  Code  Section
          280G(b)(3).


          (d) "Good Reason" shall mean any of the  following  events,  which has
not been consented to in advance by the Employee in writing: (i) the requirement
that  the  Employee  move her  personal  residence,  or  perform  her  principal
executive  functions,  more than thirty (30) miles from her primary office as of
the date of the Change in Control;  (ii) a material  reduction in the Employee's
base  compensation  as in effect on the date of the  Change in Control or as the
same may be  increased  from time to time;  (iii) the failure by the Bank or the
Company to continue to provide  the  Employee  with  compensation  and  benefits
provided for on the date of the Change in Control,  as the same may be increased
from time to time, or with benefits  substantially  similar to those provided to
her  under  any of the  employee  benefit  plans in which  the  Employee  now or
hereafter becomes a participant,  or the taking of any action by the Bank or the
Company  which  would  directly  or  indirectly  reduce any of such  benefits or
deprive the Employee of any material  fringe benefit  enjoyed by her at the time
of the Change in  Control;  (iv) the  assignment  to the  Employee of duties and
responsibilities  materially  different from those normally  associated with her
position;   (v)  a  material   diminution   or  reduction   in  the   Employee's
responsibilities  or  authority   (including   reporting   responsibilities)  in
connection with her employment with the Bank or the Company;  or (vi) a material
reduction in the secretarial or other administrative support of the Employee.


          (e) "Just Cause" shall mean,  in the good faith  determination  of the
Bank's Board of Directors,  the Employee's  personal  dishonesty,  incompetence,
willful  misconduct,   breach  of  fiduciary  duty  involving  personal  profit,
intentional failure to perform stated duties, willful violation of any law, rule
or  regulation  (other than  traffic  violations  or similar  offenses) or final
cease-and-desist  order,  or material breach of any provision of this Agreement.
The Employee shall have no right to receive  compensation  or other benefits for
any period after  termination  for Just Cause. No act, or failure to act, on the
Employee's part shall



be considered  "willful" unless she has acted, or failed to act, with an absence
of good faith and without a reasonable  belief that her action or failure to act
was in the best interest of the Bank and the Company.


          (f)  "Protected  Period" shall mean the period that begins on the date
that is the earlier of (i) the date that the Bank or the  Company  enters into a
binding,  definitive  written agreement for a Change in Control or (ii) the date
that a Change in Control occurs, and ends on the first annual anniversary of the
consummation of a Change in Control (the "Anniversary Date").


          (g) "Trust"  shall mean a grantor trust  designed in  accordance  with
Revenue  Procedure  92-64 and having a trustee  independent  of the Bank and the
Company.


     2. Trigger Events


     The Employee shall be entitled to collect the severance  benefits set forth
in Section 3 of this  Agreement in the event that (i) the  Employee  voluntarily
terminates  employment  within 90 days of an event that both  occurs  during the
Protected Period and constitutes Good Reason, or (ii) the Bank, the Company,  or
their  successor(s)  in interest  terminate the  Employee's  employment  for any
reason other than Just Cause during the Protected Period.


     3. Amount of Severance Benefit


     If the Employee becomes entitled to collect severance  benefits pursuant to
Section 2 hereof,  the Company  shall,  if not paid by the Bank  pursuant to the
severance  agreement  between  the  Employee  and the Bank,  pay the  Employee a
severance benefit equal to the difference  between the Code Section 280G Maximum
and the sum of any other  "parachute  payments"  as defined  under Code  Section
280G(b)(2) that the Employee receives on account of the Change in Control.


     The amount  payable  under this  Section 3 shall be paid  either (i) in one
lump sum within  ten days of the later of the date of the Change in Control  and
the Employee's  last day of employment with the Bank or the Company or successor
thereto,  or (ii) if prior to the date which is 90 days before the date on which
a Change in Control  occurs,  the  Employee  filed a duly  executed  irrevocable
written  election in the form  attached  hereto as Exhibit "A",  payment of such
amount shall be made according to the elected  schedule.  Deferred amounts shall
bear interest  from the date on which they would  otherwise be payable until the
date paid at a rate equal to 120% of the  applicable  federal  rate,  compounded
semiannually,  as  determined  under Code  Section  1274(d) and the  regulations
thereunder.


     In the event  that the  Employee,  Bank,  and the  Company  agree  that the
Employee has collected an amount  exceeding  the Code Section 280G Maximum,  the
parties may jointly agree in writing that such excess shall be treated as a loan
ab initio which the Employee  shall repay to the Bank,  on terms and  conditions
mutually  agreeable to the parties,  together  with  interest at the  applicable
federal rate provided for in Section 7872(f)(2)(B) of the Code.


     4. Funding of Grantor Trust upon Change in Control


     Not later  than ten  business  days  after  the last day of the  Employee's
employment  with Bank or the Company,  the Bank shall (i) deposit in a Trust the
amount of the severance  benefit specified in Section 3, unless the Employee has
previously  provided a written release of any claims under this  Agreement,  and
(ii)  provide  the  trustee of the Trust with a written  direction  to hold said
amount and any investment return thereon in a segregated account for the benefit
of the Employee, and to follow the procedures set forth in the next paragraph as
to the payment of such amounts  from the Trust.  Upon the earlier of the Trust's
final  payment  of  all  amounts  due  under  the  following  paragraph  or  the
Anniversary  Date,  the  trustee  of the Trust  shall pay to the Bank the entire
balance  remaining in the segregated  account  maintained for the benefit of the
Employee. The Employee shall thereafter have no further interest in the Trust.


     During the  12-consecutive  month period after  consummation of a Change in
Control, the Employee may provide the trustee of the Trust with a written notice
requesting  that the trustee pay to the  Employee  an amount  designated  in the
notice as being payable  pursuant to this Agreement.  Within three business days
after  receiving said notice,  the trustee of the Trust shall send a copy of the
notice to the Bank via overnight and registered  mail return receipt  requested.
On the tenth  (10th)  business day after  mailing  said notice to the Bank,  the
trustee of the Trust shall pay the  Employee  the amount  designated  therein in
immediately  available funds, unless prior thereto the Bank provides the trustee
with a written  notice  directing the trustee to withhold  such payment.  In the
latter  event,  the trustee shall submit the dispute to  non-appealable  binding
arbitration for a determination  of the amount payable to the Employee  pursuant
to this Agreement,  and the costs of such arbitration shall be paid by the Bank.
The  trustee  shall  choose  the  arbitrator  to settle  the  dispute,  and such
arbitrator shall be bound by the rules of the American  Arbitration  Association
in making his or her  determination.  The parties and the trustee shall be bound
by the results of the arbitration and, within three days of the determination by
the arbitrator,  the trustee shall pay from the Trust the amounts required to be
paid to the  Employee  and/or  the Bank,  and in no event  shall the  trustee be
liable to either party for making the payments as determined by the arbitrator.


     5. Term of the  Agreement.  This  Agreement  shall remain in effect for the
period  commencing  on the  Effective  Date and ending on the earlier of (i) the
date 36  months  after  the  Effective  Date,  and (ii)  the  date on which  the
Employee's  employment  with the Bank  terminates;  provided that the Employee's
rights hereunder shall continue following the termination of her employment with
the Bank or the Company  under any of the  circumstances  described in Section 2
hereof.  Additionally,  on each annual

                                       2


anniversary  date from the Effective  Date, the term of this Agreement  shall be
extended for an additional one-year period beyond the then effective  expiration
date  provided the Board of  Directors of the Bank and the Company  determine in
duly  adopted  resolutions  that the  performance  of the  Employee  has met the
requirements  and standards of the  respective  boards,  and that this Agreement
shall be extended.


     6. Termination or Suspension Under Federal Law.  Nothwithstanding any other
provision of this Agreement to the contrary:


          (a)  Notwithstanding  the foregoing,  but only to the extent  required
under federal banking law, the benefits payable  hereunder to the Employee shall
be reduced to the extent  that  either (A) the  present  value of such  benefits
exceeds the  limitations  set forth in Regulatory  Bulletin 27a of the Office of
Thrift  Supervision  ("OTS"),  as in effect on the  Effective  Date, or (B) such
reduction is necessary  to avoid  subjecting  the Bank or the Company to loss of
any deductions pursuant to Section 280G of the Internal Revenue Code of 1986, as
amended.


          (b) The Employee shall have no right to receive  compensation or other
benefits for any period after termination for Just Case.


          (c) Any payments made to the Employee  pursuant to this Agreement,  or
otherwise,  are subject to and conditioned  upon their compliance with 12 U.S.C.
Section 1828(k) and any regulations promulgated thereunder.


          (d) If the  Employee is removed  and/or  permanently  prohibited  from
participating  in the  conduct of the Bank's  affairs by an order  issued  under
Sections  8(e)(4) or 8(g)(1) of the Federal  Deposit  Insurance Act ("FDIA") (12
U.S.C.  1818(e)(4) or (g)(1)),  all obligations of the Bank under this Agreement
shall terminate, as of the effective date of the order, but the vested rights of
the parties shall not be affected.


          (e) If the Bank is in default (as defined in Section 3(x)(1) of FDIA),
all obligations  under this Agreement shall terminate as of the date of default;
however, this Paragraph shall not affect the vested rights of the parties.


          (f) If a notice served under Section 8(e)(3) or (g)(1) of the FDIA (12
U.S.C. 1818(e)(3) and (g)(1)) suspends and/or temporarily prohibits the Employee
from participating in the conduct of the Bank's affairs,  the Bank's obligations
under this Agreement  shall be suspended as of the date of such service,  unless
stayed by appropriate  proceedings.  If the charges in the notice are dismissed,
the  Bank  may in its  discretion  (i)  pay  the  Employee  all or  part  of the
compensation  withheld while its contract  obligations were suspended,  and (ii)
reinstate  (in whole or in part) any of its  obligations  which were  suspended.
However, this paragraph shall not affect the vested rights of the parties.


          (g) All obligations  under this Agreement shall be terminated,  except
to the extent  determined  that  continuation of this Agreement is necessary for
the continued operation of the Bank: (A) by the Director of the OTS or her other
designee,  at the time the Federal Deposit Insurance  Corporation enters into an
agreement to provide  assistance to or on behalf of the Bank under the authority
contained in section 13(c) of the FDIA; or (B) by the Director of the OTS or her
designee, at the time the Director or her designee approves a supervisory merger
to  resolve  problems  related  to  operation  of the  Bank or when  the Bank is
determined by the Director to be in an unsafe or unsound  condition.  Any rights
of the parties that have already vested,  however, shall not be affected by such
action.


     7. Expense Reimbursement.


          In the event that any dispute arises between the Employee and the Bank
or the  Company as to the terms or  interpretation  of this  Agreement,  whether
instituted by formal legal  proceedings or otherwise,  including any action that
the Employee  takes to enforce the terms of this  Agreement or to defend against
any action taken by the Bank or the Company,  the Employee  shall be  reimbursed
for all costs and expenses,  including reasonable  attorneys' fees, arising from
such dispute,  proceedings or actions, provided that the Employee shall obtain a
final judgement in favor of the Employee in a court of competent jurisdiction or
in binding arbitration under the rules of the American Arbitration  Association.
Such reimbursement  shall be paid within ten (10) days of Employee's  furnishing
to the Bank and the Company written  evidence,  which may be in the form,  among
other things, of a cancelled check or receipt, of any costs or expenses incurred
by the Employee.


     8. Successors and Assigns.


          (a) This  Agreement  shall inure to the benefit of and be binding upon
any  corporate or other  successor of the Bank or Company  which shall  acquire,
directly or indirectly, by merger, consolidation,  purchase or otherwise, all or
substantially all of the assets or stock of the Bank or Company.


          (b) Since the Bank is contracting  for the unique and personal  skills
of the Employee,  the Employee  shall be precluded  from assigning or delegating
her rights or duties  hereunder  without first  obtaining the written consent of
the Bank.

                                       3



     9.  Consideration from Company:  Joint and Several Liability.  In the event
that the Bank does not pay the benefits due to the Employee  under  Section 3 of
this Agreement,  the Company hereby agrees that to the extent  permitted by law,
it shall be jointly  and  severally  liable with the Bank for the payment of all
amounts due under this Agreement.


     10.  Amendments.  No  amendments  or additions to this  Agreement  shall be
binding  unless  made in  writing  and signed by all of the  parties,  except as
herein otherwise specifically provided.


     11. Applicable Law. Except to the extent preempted by Federal law, the laws
of the State of Arkansas shall govern this Agreement in all respects, whether as
to its validity, construction, capacity, performance or otherwise.


     12.  Severability.  The  provisions  of  this  Agreement  shall  be  deemed
severable and the  invalidity  or  unenforceability  of any provision  shall not
affect the validity or enforceability of the other provisions hereof.


     13. Entire  Agreement.  This Agreement,  together with any understanding or
modifications  thereof as agreed to in writing by the parties,  shall constitute
the entire agreement between the parties hereto.


     IN WITNESS WHEREOF, the parties have executed this Agreement on the day and
year first hereinabove written.





ATTEST:                                 HEARTLAND COMMUNITY BANK


/s/ Paula J. Bergstrom                 By: /s/ Vida H. Lampkin
- ----------------------------------        -------------------------------------
Secretary                                 Its Chairman of the Board



ATTEST:                                 HCB BANCSHARES, INC.


/s/ Paula J. Bergstrom                 By: /s/ Vida H. Lampkin
- ----------------------------------        -------------------------------------
Secretary                                 Its Chairman of the Board



WITNESS:                                EMPLOYEE


/s/ Kevin W. Pletcher                   /s/ Paula J. Bergstrom
- ----------------------------------      ---------------------------------------
                                        Paula J. Bergstrom


                                       4


                                                                     EXHIBIT "A"


                              HCB BANCSHARES, INC.
                            HEARTLAND COMMUNITY BANK
                     CHANGE-IN-CONTROL PROTECTIVE AGREEMENT

                         -------------------------------

                         DEFERRED PAYMENT ELECTION FORM

                         -------------------------------


     AGREEMENT,  made  this  19th day of July,  2001,  by and  between  Paula J.
Bergstrom  (the  "Employee"),  HEARTLAND  Community  Bank (the  "Bank")  and HCB
Bancshares,   Inc.  (the  "Company"),  with  respect  to  payment  of  severance
compensation  to the  Employee  pursuant  to Section 3 of her  change-in-control
protective agreement  ("Agreement") with the Bank and the Company dated July 19,
2001.


     NOW THEREFORE, it is mutually agreed as follows:


     1. Form of Payment.  The Employee,  by the execution  hereof, in accordance
with Section 3 of the Agreement,  elects to have her change in control severance
benefits (plus earnings thereon) distributed in cash as follows:


          __________in one lump sum payment.


          __________in  substantially  equal  annual  payments  over a period of
          _____ years (no more than 10).


     2. In the event of the Employee's  death, her benefits shall be distributed
- --        __________in one lump sum payment.

          __________in   accordance  with  the  payment  schedule   selected  in
          paragraph 1 hereof (with payments made as though the Employee survived
          to collect all benefits, and as though the Employee terminated service
          on the date of her death, if payments had not already begun).


     3. Designation of Beneficiary.  In the event of the Employee's death before
she has collected all of the benefits payable pursuant to the Agreement and this
election,  any such benefits  payable shall be distributed to the beneficiary or
beneficiaries  designated under subparagraphs a and b of this paragraph 3 in the
manner elected pursuant to paragraph 2 above:


     a. Primary Beneficiary.  The Employee hereby designates the person(s) named
below to be her  primary  beneficiary  and to receive  the balance of any unpaid
benefits under the Agreement:

- ----------------------------- --------------------------- ---------------------
           Name of                  Mailing Address             Percentage of
     Primary Beneficiary                                        Death Benefit
- ----------------------------- --------------------------- ---------------------
                                                                              %

- ----------------------------- --------------------------- ---------------------
                                                                              %

- ----------------------------- --------------------------- ---------------------

     b.  Contingent  Beneficiary.  In the event that the primary  beneficiary or
beneficiaries  named above are not living at the time of the  Employee's  death,
the Employee  hereby  designates  the following  person(s) to be her  contingent
beneficiary for purposes of the Agreement:

- ------------------------------- -------------------------- --------------------
            Name of                  Mailing Address             Percentage of
     Contingent Beneficiary                                      Death Benefit
- ------------------------------- -------------------------- --------------------
                                                                              %

- ------------------------------- -------------------------- --------------------
                                                                              %

- ------------------------------- -------------------------- --------------------

     4. Effect of  Election.  The  elections  made in  paragraph 1 hereof  shall
become irrevocable 90 days prior to the change in control.  The Employee may, by
submitting an effective  superseding  Deferred Payment Election Form at any time
and from time to time,  prospectively change the beneficiary designation and the
manner of  payment to a  beneficiary.  Such  elections  shall,  however,  become
irrevocable upon the Employee's death.


     5.  Commitments.  The Bank and the  Company  agree to make  payment  of all
amounts due the Employee in  accordance  with the terms of the Agreement and the
elections made by the Employee herein.



     IN WITNESS  WHEREOF,  the parties  hereto have hereunto set their hands the
day and year first above-written.


WITNESS:                                                EMPLOYEE



/s/ /s/ Paula J. Bergstrom              By:  /s/ Paula J. Bergstrom
- ----------------------------------         -------------------------------------
                                           Paula J. Bergstrom



WITNESS:                                HEARTLAND COMMUNITY BANK



/s/ Paula J. Bergstrom                  By: /s/ Vida H. Lampkin
- ----------------------------------        -------------------------------------
                                          Its Chairman of the Board



ATTEST:                                 HCB BANCSHARES, INC.


/s/ Kevin W. Pletcher                   By: /s/ Vida H. Lampkin
- ----------------------------------        -------------------------------------
                                          Its Chairman of the Board