TERMINATION AND RELEASE AGREEMENT

Exhibit 10.12

TERMINATION AND RELEASE AGREEMENT

This Termination Agreement (the “Agreement”) is entered into as of the 1^st day of January, 2005, by and among Larry R. Mathews (“Employee”), Heritage Financial Holding Corporation, a Delaware corporation (“HFHC”), and Heritage Bank, an Alabama state banking corporation (“Heritage Bank”).

WHEREAS, Employee has been employed by HFHC and Heritage Bank pursuant to an Employment Agreement dated January 23, 2003, by and among HFHC, Heritage Bank and Employee (the “Prior Employment Agreement”); and

WHEREAS, pursuant to that certain Agreement and Plan of Merger, dated July 15, 2004, as amended (the “Merger Agreement”), by and among The Peoples Holding Company, a Mississippi corporation (“Peoples”), The Peoples Bank & Trust Company, a Mississippi banking association (the “Company”), HFHC and Heritage Bank, a certain Plan of Merger shall be effectuated with regard to such parties as of the “Effective Time” (as defined in Section 1.2 of the Merger Agreement); and

WHEREAS, Employee has entered into an Employment Agreement among Employee and Peoples and the Company (the “New Employment Agreement”) which New Employment Agreement is conditioned upon the consummation of the said Plan of Merger and shall be effective as of the Effective Time; and

WHEREAS, as an inducement to Peoples and the Company to enter into the Merger Agreement and to execute and deliver the New Employment Agreement, and for other valuable consideration, the receipt and sufficiency of which is hereby acknowledged, the parties hereto wish to settle and release any and all claims any party hereto may have against another party hereto arising from Employee’s employment with HFHC and Heritage Bank and the termination of the Prior Employment Agreement, upon the following terms and provisions:

1. Prior Agreements. The parties hereto agree that the Prior Employment Agreement shall be terminated and of no further force and effect as of the Effective Time. This Agreement shall be null and void ab initio and of no further force and effect if the Effective Time does not occur or the Merger Agreement is terminated prior to the Effective Time.

2. No Additional Payment or Benefits. No payments or benefits shall be made by the HFHC or Heritage Bank to Employee, and Employee acknowledges that he has no entitlement to, or any right to make any claims for any additional payments or benefits from HFHC or Heritage Bank of any kind whatsoever.

3. Release and Indemnification by Employee.

A. In consideration of the promises contained herein and in the New Employment Agreement, Employee, on behalf of himself and his heirs, executors,

administrators, successors and assigns, hereby fully and forever discharges and irrevocably releases HFHC and Heritage Bank and all of their directors, officers, employees, shareholders, affiliates, successors and assigns (the “Released Parties”) from any and all claims, demands, actions, suits, causes of action and liabilities of whatever kind and nature, whether in law or in equity and whether known or unknown, which he had, now has or hereafter can, shall or may have against HFHC and Heritage Bank, for, upon or by reason of or arising out of Employee’s employment with Heritage Bank and the termination of the Prior Employment Agreement, including, but not limited to, claims in equity or law for personal injury, breach of contract, whether express or implied, or oral or written, fraudulent inducement, defamation, mental anguish, intentional infliction of emotional distress, prima facie tort, intentional interference with contractual relations, injury to health and reputation, claims under federal, state or local laws prohibiting discrimination on the account of age, national origin, race, sex, handicap, religion, and similar classifications, claims under the Civil Rights Act of 1866, the Civil Rights Act of 1964, Title VII, as amended, the Civil Rights Act of 1991, the Age Discrimination in Employment Act of 1967, as amended (“ADEA”), the Employee Retirement Income Security Act of 1974, as amended, the Family and Medical Leave Act of 1994, and the Americans With Disabilities Act. The provisions of any laws providing in substance that releases shall not extend to claims which are unknown or unsuspected at the time to the person executing such waiver or release, are hereby expressly waived; provided, however that this release shall not extend to rights or claims under ADEA that may arise after the date of this Agreement. Employee hereby agrees to forego any right to file any charges or complaint with any governmental agencies for a lawsuit against the Released Parties under any of the laws referenced in this paragraph or with respect to any matters covered by the release in this paragraph to the extent such laws or matters relate to employment under the Prior Employment Agreement.

B. Employee shall indemnify and hold harmless each of the Released Parties from and against all loss, liability, claim, damage or expense (including costs of investigation and defense and reasonable attorneys’ fees), arising directly or indirectly from or in connection with the assertion by or on behalf of Employee of any claim or other matter purported to be released pursuant to this Agreement.

C. Employee hereby irrevocably covenants to refrain from, directly or indirectly, asserting any claim or demand, or commencing, instituting or causing to be commenced, any proceeding of any kind against any of the Released Parties based upon any matter purported to be released hereby.

4. Release and Indemnification by HFHC and Heritage Bank.

A. In consideration of the promises contained herein, HFHC and Heritage Bank, and their respective successors and assigns, hereby fully and forever discharge and irrevocably release Employee from any and all claims, demands, actions, suits, causes of action and liabilities of whatever kind and nature, whether in law or in equity and whether known or unknown, which either had, now has or hereafter can, shall or may have against Employee, for, upon or by reason of or arising out of Employee’s employment with HFHC or Heritage Bank and the termination of the Prior Employment Agreement. The provisions of any laws providing in substance that releases shall not extend to claims which are unknown or unsuspected at the time to the person executing such waiver or release, are hereby expressly waived. HFHC and

2

Heritage Bank, and their respective successors and assigns, hereby agree to forego any right to file any charges or complaint with any governmental agencies for a lawsuit against the Employee under any of the laws referenced in this paragraph or with respect to any matters covered by the release in this paragraph to the extent such laws or matters relate to employment under the Prior Employment Agreement.

B. HFHC and Heritage Bank, and their respective successors and assigns, shall indemnify and hold harmless Employee from and against all loss, liability, claim, damage or expense (including costs of investigation and defense and reasonable attorneys’ fees), arising directly or indirectly from or in connection with the assertion by or on behalf of HFHC or Heritage Bank, or their respective successors and assigns, of any claim or other matter purported to be released pursuant to this Agreement.

C. HFHC and Heritage Bank, and their respective successors and assigns, hereby irrevocably covenant to refrain from, directly or indirectly, asserting any claim or demand, or commencing, instituting or causing to be commenced, any proceeding of any kind against Employee based upon any matter purported to be released hereby.

5. Rights Under Agreement and New Employment Agreement. Notwithstanding any provision contained herein to the contrary, the release by Employee in this Agreement shall not limit the right of Employee to seek or enforce the provisions of this Agreement or the New Employment Agreement.

6. Governing Law. The validity, interpretation, construction, and performance of this Agreement shall be governed by the laws of the State of Alabama without regard to principles of conflict of laws.

7. Entire Agreement. Each party hereto acknowledges that such party is entering into this Agreement voluntarily and that such party fully understands all of its provisions. This Agreement constitutes the entire understanding of the parties and supersedes all prior oral and written agreements. This Agreement cannot be modified except by a writing signed by all parties hereto.

8. Amendment. No provisions of this Agreement may be amended, modified, waived or discharged except by a written document signed by all the parties hereto.

9. Severability. The invalidity or unenforceability of any provision of this Agreement shall not affect the validity or enforceability of any other provision of this Agreement, which shall remain in full force and effect to the fullest extent permitted by law.

10. Survival of Rights and Obligations. The rights and obligations of the parties under the provisions of this Agreement shall survive, and remain binding and enforceable, notwithstanding the termination of the Employee’s employment with HFHC or Heritage Bank or any settlement of the financial rights and obligations arising from the Employee’s employment with HFHC or Heritage Bank, to the extent necessary to preserve the intended benefits of such provision.

3

11. Counterparts. This Agreement may be executed (including via facsimile) in one or more counterparts, each of which shall be deemed to be an original, but all of which together shall constitute one and same instrument, and, subject to the further terms of this Agreement, shall become effective when one or more counterparts have been signed by each of the parties and delivered to the other parties.

12. Headings. The headings and title of this Agreement are inserted for convenience only and shall not affect in any way the meaning or interpretation of this Agreement.

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be duly executed on the date first above written.

4