SEPARATION AGREEMENT

Exhibit 10.1

SEPARATION AGREEMENT

THIS SEPARATION AGREEMENT (this “Agreement”) is made and entered into by and between Stein Mart, Inc., a Florida corporation, including its officers, directors, owners, employees, agents, representatives, subsidiaries, affiliates, successors and assigns (hereinafter, jointly and severally, “Stein Mart”) and William A. Moll (“Moll”), a Florida resident. The effective date of this Agreement shall be February 2, 2010 (the “Effective Date”).

RECITALS

A. Stein Mart employed Moll pursuant to that certain Stein Mart, Inc. Employment Agreement dated September 15, 2009 and as amended in December, 2005 (the “Employment Agreement”).

B. In association with Moll’s separation from employment, Stein Mart and Moll desire to resolve all differences between them, if any, arising from the date Moll was employed by Stein Mart through the Effective Date.

C. This Agreement sets forth the terms and obligations of the parties to each other from the Effective Date forward.

Terms of Agreement

In consideration of the promises contained in this Agreement, the receipt and sufficiency of which are hereby acknowledged, Stein Mart and Moll now agree as follows:

1. Recitals. The Recitals are true and accurate and incorporated into this Agreement.

2. Separation. Moll has voluntarily separated from employment on the Effective Date. Stein Mart and Moll have mutually agreed that Moll shall be deemed terminated “without cause” pursuant to Section 5(b) of the Employment Agreement.

3. Modification of Employment Agreement. This Agreement supplements the Employment Agreement and in the event of any inconsistencies between the terms of this Agreement and the terms of the Employment Agreement, this Agreement shall control.

4. Compensation. Stein Mart will make all payments to Moll and provide such benefits during the Continuation Period (as that term is defined in the Employment Agreement) as though Moll was terminated “without cause” pursuant to Section 5(b) of the Employment Agreement notwithstanding the voluntary nature of Moll’s termination.

5. Vesting under 2009 Incentive Plan. Moll shall be entitled to all Performance Shares granted under Stein Mart’s 2009 Incentive Compensation Plan

which vest as of the end of Stein Mart’s 2009 fiscal year being half of the Performance Shares Moll would have received under that plan had he remained employed through the end of fiscal 2010.

6. Compensation for Vacation or Leave Time. The compensation provided hereunder includes pay for accrued, but unused vacation time. As a result, Moll shall receive no separate compensation for vacation and/or leave time, and Moll waives any claim for compensation therefore.

7. No Claim for Wages or Compensation. Moll acknowledges that through the Effective Date he has received all wages, salary or other compensation which he is due or to which he believes he may be entitled. Moll waives any claim for any other wages, salary or other compensation earned or accrued through the Effective Date.

8. Pension, Retirement or Deferred Compensation Benefits. Moll is not a participant in or beneficiary of any defined benefit pension or retirement plan. Moll participated in Stein Mart’s 401(k) plan. Moll shall be entitled to exercise rights under Stein Mart’s 401(k) plan available to him as a separating employee. Stein Mart shall not make any 401(k) matching contributions with respect to Moll’s compensation for fiscal 2009. Moll does not waive any compensation or benefits available to him under the Executive Deferred Compensation Plan which shall be payable to him according to its terms. Stein Mart will not make matching contributions to the Deferred Compensation Plan for Moll’s benefit with respect to fiscal 2009.

9. No Claim for Disability or Workers’ Compensation Benefits. Moll represents that he is not currently experiencing any condition, injury or illness for which he has, or in his reasonable opinion could or should seek short or long-term disability benefits. Moll acknowledges that as of the Effective Date he has not filed any claim for short or long-term disability benefits. Moll represents that he has not suffered or experienced any illness or injury in connection with his employment with Stein Mart for which he has or could, in his reasonable opinion, seek workers’ compensation benefits. Moll acknowledges that as of the Effective Date he has not filed any claim for workers’ compensation benefits. This Agreement does not require Moll to waive any claim for workers’ compensation benefits.

10. Equity Based Compensation. Moll has been granted those performance shares, restricted shares and non-qualified stock options shown on Schedule A attached hereto (the “Equity Schedule”), all of which were granted under the 2001 Stein Mart, Inc. Omnibus Plan. Moll has exercised those grants shown as exercised on the Equity Schedule as of the Effective Date. Moll acknowledges and agrees he voluntarily exercised those grants. Moll further acknowledges and agrees that he received fair and adequate disclosure about Stein Mart, including financial information, prior to deciding to exercise his grants and received fair and adequate compensation from such exercise. Moll waives and will not make any claim for damages relating to his prior exercise of these grants at any time prior to the execution of this Agreement. Moll also acknowledges that he will forfeit those grants shown on the Equity Schedule as unvested

2

and that he has a limited time to exercise unexercised options shown on the Equity Schedule as provided in the grant documents relating to such options.

11. Exercise of Remaining Options. Pursuant to the 2001 Stein Mart, Inc. Omnibus Plan Moll may exercise his remaining options on or before [May 2, 2010]. Such exercise, if any, shall comply with the terms of the 2001 Stein Mart, Inc. Omnibus Plan.

12. Representations and Warranties. As a material part of this Separation Agreement, Moll represents and warrants:

a. Moll has not received notice of a pending charge, complaint or case filed against him by any administrative, regulatory, investigative or governmental agency or body relating to his conduct as an employee or officer of Stein Mart.

b. Moll has not filed any charge or complaint against Stein Mart with any administrative, regulatory, investigative or governmental agency or body.

c. Moll does not know and is not aware of any violation of local, state or federal rule, ordinance, statute, regulation or law by Stein Mart.

d. Moll is not aware of any activity, practice or policy of Stein Mart that he reasonably believes involve mail fraud, wire fraud or securities fraud, or violate any rule or regulation of the Securities and Exchange Commission or any provisions of Federal law relating to fraud against shareholders.

e. Except for those matters that reasonably arose within the exercise of his duties, Moll has not made any binding obligation to any person on behalf of Stein Mart that has not been disclosed in writing to the Chief Financial Officer, Executive Vice-President, Chief Administrative Officer or General Counsel of Stein Mart.

f. Moll has not knowingly engaged in any activity that would reasonably be construed as acting outside the scope of his employment with Stein Mart.

g. All information disclosed by Moll or known by him to have been disclosed by others to attorneys for Stein Mart in connection with any pending litigation or investigation is, to the best of his knowledge, correct, truthful and has been provided to Stein Mart.

h. Moll does not know and is not aware of any violation of a generally accepted accounting principle committed by Stein Mart.

i. Moll is not aware of any complaint, case or charge filed against a customer, manufacturer or vendor of Stein Mart in which Stein Mart is named, or reasonably could be named, as an interested or involved party.

3

j. Moll has disclosed in writing to the Chief Financial Officer, Executive Vice President, Chief Administrative Officer or General Counsel all issues that Moll reasonably anticipates could have a material impact on Stein Mart’s stock price. For purposes of this paragraph Moll will be held to a standard of care consistent with his position of Sr. Vice President, General Merchandising Manager of a publicly traded company, as compared to other professionals holding or having similar professional backgrounds as Moll.

k. The representations and warranties are true and correct as of the date Moll signs this Agreement.

13. Continuing Duty as to Representations and Warranties. During the Continuation Period Moll has an affirmative obligation and duty to notify the General Counsel of Stein Mart in writing of any change or event that would alter or cause to be untrue or incomplete the Representation and Warranties specified in paragraph 12. Written notice shall be provided within three days of the event or knowledge giving rise to the notice required to be given.

14. Duty to Cooperate. From the Effective Date and until all payments due Moll under this Agreement are paid Moll has an affirmative duty to cooperate with Stein Mart and will be available for consultation on all business related matters, including but not limited to matters currently in litigation or subject to administrative or regulatory investigation or involving matters that arose during his employment with Stein Mart, all charges or litigation pending at the Effective Date or subsequently filed but based on events occurring prior to the Effective Date, or other matters (not limited to litigation) that fell within the purview of Moll acting as a Senior Vice President of Stein Mart. Stein Mart shall make requests for Moll’s cooperation in “good faith.” Moll will respond promptly to such requests when made. Requests for cooperation will be made to Moll by the General Counsel, CEO or Executive Vice President, Chief Administrative Officer or designees of each. Moll’s duty to cooperate is a material term of this Agreement.

15. Duty to Testify or Participate. From the Effective Date and until all payments due Moll under this Agreement are paid Moll has an affirmative duty to cooperate or truthfully testify as the request or obligation may arise. Moll’s duty to testify or participate is a material term of this Agreement.

16. Reimbursement of Expenses. Moll acknowledges and agrees that as of the Effective Date he has submitted all expenses incurred prior to the Effective Date and is not owed reimbursement for any expense. Thereafter, and continuing until all payments required by this Agreement are paid, Stein Mart will reimburse Moll for reasonable expenses, if any, provided such expenses are (a) approved in advance by the CEO of Stein Mart or his designee; and (b) are submitted to the Executive Vice President, Chief Administrative Officer for reimbursement within five (5) days of the expenditure.

17. Non Disparagement. Stein Mart and Moll agree that neither will make or publicize any statements that are in any way disparaging or negative toward each other

4

or Stein Mart’s services, products, officers, employees or representatives. The type of disparaging comments contemplated includes, but is not limited to, any remark which may cause or tend to cause an adverse impact on the reputation or character of Stein Mart or Moll or cause a reasonable person in the community to negatively alter or change his or her opinion of Stein Mart or Moll. Moll’s duty not to disparage is a material term of this Agreement and extends by him toward Stein Mart’s officers, directors, employees, shareholders, directors, managers, assigns and shareholders.

18. Subordination. Any payment obligations incurred by Stein Mart under this Agreement shall be subordinate to all other borrowings of Stein Mart.

19. Equitable Remedies. Moll and Stein Mart agree that it is not possible to measure in money the damages which will accrue to Stein Mart if Moll breaches or threatens breach of any of the covenants, agreements, or obligations set forth in this Agreement. Accordingly, if any action or proceeding is commenced to enforce any of the provisions contained in this Agreement, Moll and Stein Mart hereby waive the claim or defense thereto that there is an adequate remedy at law or that there has not been irreparable damage by such breach or threatened breach.

20. Notices. All notices, demands, communications required or preferred to be given in connection with this Agreement shall be in writing and shall be sent as follows:

or to such other person at such location as either party subsequently designates in writing to the other.

21. Governing Law. This Agreement shall be interpreted and governed by the laws of the State of Florida, without regard to its conflicts of law principles. Venue for any action shall be exclusively in the state or federal courts in and for Duval County, Florida. Without limitation, the provisions of Section 7(h) of the Employment Agreement (relating in part to the waiver of jury trial) are incorporated herein.

22. Severability. In the event any provision of this Agreement is found to be invalid, illegal or unenforceable in any respect, the validity, legality and enforceability of the remaining provisions contained herein shall not in any way be affected or impaired. Further, any provision found to be invalid, illegal or unenforceable shall be deemed, without further action on the part of the parties hereto, to be modified, amended and/or limited to the minimum extent necessary to render such clauses and/or provisions valid and enforceable.

5

23. Entire Agreement. Except as specifically provided herein, this Agreement supersedes all prior written and verbal promises and agreements which may exist between Stein Mart and Moll. This Agreement and the Employment Agreement constitute the entire agreement between the parties relating to the cessation of Moll’s employment and this Agreement may be amended, modified or superseded only by a written agreement signed by both parties. No oral statements by Moll or by any employee of Stein Mart shall modify or otherwise affect the terms and provisions of this Agreement.

24. Binding Effect. This Agreement shall bind and benefit the heirs, personal representatives, administrators, successors, subsidiaries, affiliates and assigns of Stein Mart and Moll.

25. Counterparts. This Agreement may be executed in multiple counterparts, each of which shall be deemed an original, and all of which together shall constitute one and the same agreement.

BEFORE SIGNING THIS AGREEMENT, MOLL ACKNOWLEDGES THE FOLLOWING:

I HAVE READ AND FULLY UNDERSTAND THIS AGREEMENT;

I HAVE BEEN ADVISED OF MY RIGHT TO CONSULT MY OWN ATTORNEY BEFORE SIGNING THIS AGREEMENT;

I AM SIGNING THIS AGREEMENT KNOWINGLY AND VOLUNTARILY.

The parties hereto have executed this Agreement as of the date set forth above.

6

Schedule A

Equity Based Compensation

7