AMENDED AND RESTATED EMPLOYMENT AGREEMENT DATED APRIL 18, 2003

EXHIBIT 10.35

AMENDED AND RESTATED

EMPLOYMENT AGREEMENT DATED APRIL 18, 2003

This Amended and Restated Employment Agreement dated April 18, 2003 (“Agreement”) is entered into as of the 18th day of April 2003, by and between Saks Incorporated (“Company”), and R. Brad Martin (“Executive”).

Company and Executive agree as follows:

1.  Employment.    Company hereby employs Executive as Chief Executive Officer of Company. It is anticipated that Executive will be elected Chairman of the Board.

2.  Duties.    During his employment, Executive shall devote substantially all of his working time, energies, and skills to the benefit of Company’s business. Executive agrees to serve Company diligently and to the best of his ability and to use his best efforts to follow the policies and directions of Company’s Board of Directors.

3.  Compensation.    Executive’s compensation and benefits under this Agreement shall be as follows:

(a)  Base Salary.    Company shall pay Executive a base salary (“Base Salary”) at a rate of no less than $1,000,000 per year. In addition, the Board of Directors of Company shall, in good faith, consider granting increases in such Base Salary based upon such factors as Executive’s performance and the growth and/or profitability of Company. Executive’s Base Salary shall be paid in installments in accordance with Company’s normal payment schedule for its senior management. All payments shall be subject to the deduction of payroll taxes and similar assessments as required by law.

(b)  Bonus.    In addition to the Base Salary, Executive shall be eligible pursuant to the 1998 Senior Executive Bonus Plan for a yearly cash bonus based upon his performance, in accordance with specific annual objectives, set in advance, all as approved by the Board of Directors.

(c)  Annual Stock Grant Bonus.    Pursuant to the 1998 Senior Executive Bonus Plan, an amount up to twenty thousand (20,000) shares of Company common stock may be issued to Executive as soon as possible after the end of each fiscal year of Company, based upon annual targeted growth in intrinsic value of the Company or other factors, as determined by the Human Resources Committee of the Board of Directors. The Human Resources Committee, subject to approval from the Board of

1

Directors, shall have sole and exclusive discretion to grant or withhold any portion of such yearly stock grant.

(d)  Second Annual Stock Grant Bonus.    Pursuant to the 1998 Senior Executive Bonus Plan, Company shall award Executive a bonus of up to 20,000 (twenty thousand) shares of Company common stock on the basis of growth in earnings per share with the Human Resources Committee of the Board of Directors setting the objectives in advance. The Human Resources Committee shall have sole and exclusive discretion to determine whether that objective has been met, and the Committee may consider matters such as nonrecurring and extraordinary items. The Human Resource Committee may allocate the 40,000 shares bonus potential in Paragraphs 3(c) and 3(d) in any manner permitted by the 1998 Senior Executive Bonus Plan so that, if less than 20,000 shares of stock may be earned under this Section 3(d), it may increase accordingly the number of shares that may be earned under Section 3(c).

(e)  Vesting of Prior Restricted Stock Grants.    Company has previously declared earned the shares of restricted stock granted under the TARSAP programs in 1996 and 1998. The remaining unvested shares under those programs shall vest on November 1, 2003, provided that Executive remains employed by Company on those dates.

(f)  Five-Year Service Stock Grant.     In accordance with Executive’s prior contract, Executive shall be awarded 250,000 shares of Company common stock on May 31, 2006, provided, however, that he does not voluntarily end his employment with Company prior to that time. In the event of Executive’s death prior to May 31, 2006, Executive’s estate shall be issued a pro rata portion of those shares.

(g)  Performance Stock Grant.    In accordance with Executive’s prior contract, Executive shall have the ability to earn up to 500,000 shares of Company common stock to be awarded on May 31, 2006. The number of shares awarded, if any, will be based on the average stock price of Company common stock from June 1, 2005, through May 31, 2006. The threshold for earning any shares shall be $17.57, with 100,000 shares being earned at that price. The maximum number of shares shall be 500,000, and that number of shares shall be earned with a stock price of $29.30 or higher. Shares shall be pro rated between $17.57 and $29.30.

2

(h)  Annual Stock Grant.    Executive shall be awarded 5,000 shares of Company common stock on May 1 of each year as long as he holds the position set forth in Paragraph 1.

(i)  Effect of Change In Control on Options and Restricted Stock.    In the event of a Change in Control (as defined in the Company’s 1994 LTIP), any Options and restricted stock granted to Executive prior to such Change In Control shall immediately vest. The number of shares awarded under subparagraph (g) shall be determined by using the purchase price of the Company’s shares.

4.  Insurance and Other Expenses and Benefits.    Company shall allow Executive to participate in each employee benefit plan and to receive each executive benefit that Company provides for senior executives at the level of Executive’s position.

(a)  Company shall not modify nor extend the Company’s split-dollar insurance obligations set forth under Section 4(a) of the Amended and Restated Employment Contract Dated May 31, 2001. For the two-year non-competition period in Section 8 below after Executive’s employment ends, Company shall reimburse Executive for an offsite office and one secretary.

(b)  Company shall provide security for Executive’s residences or shall reimburse Executive for such expenses.

(c)  Executive shall be entitled to lifetime participation in Company’s health plan in the event that he retires from Company.

(d)  Executive shall be entitled to a lifetime associate discount for merchandise purchased from Company, and this provision shall survive termination of employment or expiration of this Agreement.

(e)  Company shall provide Executive with long-term disability insurance with a benefit of $30,000 per month. Company shall also pay for a required annual physical examination of Executive.

5.  Term; termination without Cause or for Good Reason.    The term of this Agreement shall run until October 1, 2007, provided, however, that Company may terminate this Agreement at any time without Cause, as defined below, upon thirty (30) days’ prior written notice and Executive may terminate this Agreement for Good Reason. Good Reason shall mean a mandatory relocation from the Memphis, Tennessee area, or at any time Executive chooses to

3

terminate employment within one year after a Change In Control of Company (as defined in the in the 1994 LTIP). Upon such termination of employment, this Agreement shall terminate except for Section 8, which shall continue in effect as set forth in Section 8. In the event of such termination by Company without Cause or by Executive for Good Reason, Executive shall be entitled, in addition to all earned but unpaid wages and benefits, to the following severance benefits:

(a)  a sum equal to the Base Salary then in effect plus 25% of Executive’s maximum bonus potential (in effect at the time) multiplied by the longer of 3 years or the balance of the time remaining in the Term, and

(b)  immediate vesting of all stock options and restricted stock awards (including service grants) with the ability to exercise the stock options for the shorter of two years or the original expiration period of the option, and

(c)  participation in Company’s health plans, with family coverage, for his life, and continuation of split-dollar insurance agreements for five years, and

(d)  reimbursement for the cost of a full-time secretary during the balance of the term of this Agreement or three years, whichever is longer, and

(e)  if any payment, right or benefit provided for in this Agreement or otherwise paid to Executive by Company is treated as an “excess parachute payment” under Section 280(G)(b) of the Internal Revenue Code of 1986, as amended, (the “Code”), Company shall indemnify and hold harmless and make whole, on an after-tax basis, Executive for any adverse tax consequences, including but not limited to providing to Executive on an after-tax basis the amount necessary to pay any tax imposed by Code Section 4999.

In addition, this Agreement shall terminate upon the death of Executive, except as to: (a) Executive’s estate’s right to exercise any unexercised stock options pursuant to Company’s stock option plan then in effect, with it being understood that Company would follow its traditional policy of vesting all of Executive’s stock options upon death, (b) other entitlements under this contract that expressly survive death, (c) payment of earned but unpaid wages and benefits, and (d) any rights which Executive’s estate or dependents may have under COBRA or any other federal or state law or which are derived independent of this Agreement by reason of his participation in any plan maintained by Company.

4

6.  Termination by Company for Cause.    (a) Company shall have the right to terminate Executive’s employment under this Agreement for Cause, in which event no salary or bonus shall be paid after termination for Cause except for (i) earned but unpaid wages and benefits, and (ii) Company shall vest a pro rata fractional portion of Executive’s stock options based on the number of days Executive was employed since the last vesting of such options. Termination for Cause shall be effective immediately upon notice sent or given to Executive. For purposes of this Agreement, the term “Cause” shall mean and be strictly limited to: conviction of Executive, after all applicable rights of appeal have been exhausted or waived, for any crime that materially discredits Company or is materially detrimental to the reputation or goodwill of Company.

(b)  In the event that Executive’s employment is terminated, Executive agrees to resign as an officer and/or director of Company (or any of its subsidiaries or affiliates), effective as of the date of such termination, and Executive agrees to return to Company upon such termination any of the following which contain confidential information: all documents, instruments, papers, facsimiles, and computerized information which are the property of Company or such subsidiary or affiliate.

7.  Disability.    If Executive becomes disabled at any time during the term of this Agreement, he shall after he becomes disabled continue to receive all payments and benefits provided under the terms of this Agreement for a period of twelve consecutive months, or for the remaining term of this Agreement, whichever period is shorter. In the event that Executive is disabled for more than twelve consecutive months during the term of this Agreement, Executive shall, at the expiration of the initial twelve consecutive month period, be entitled to receive under this Agreement 50% of his Base Salary plus the insurance and benefits described in Section 4 of this Agreement for the remaining term of this Agreement. While Executive is disabled, he shall remain employed for purposes of vesting of restricted stock and stock options, and, after his employment ends, he shall be entitled to the lifetime benefits set forth in Section 5(c). For purposes of this Agreement, the term “disabled” shall mean the inability of Executive (as the result of a physical or mental condition) to perform the duties of his position under this Agreement with reasonable accommodation and which inability is reasonably expected to last at least one (1) full year.

8.  Non-competition; Unauthorized Disclosure.

5

(a)  Non-competition.    During the period Executive is employed under this Agreement, and for a period of two years thereafter, Executive:

(i)  shall not engage in any activities, whether as employer, proprietor, partner, stockholder (other than the holder of less than 5% of the stock of a corporation the securities of which are traded on a national securities exchange or in the over-the-counter market), director, officer, employee or otherwise, in competition with (i) the businesses conducted at the date hereof by Company or any subsidiary or affiliate, or (ii) any business in which Company or any subsidiary or affiliate is substantially engaged at any time during the employment period;

(ii)  shall not solicit, in competition with Company, any person who is a customer of the businesses conducted by Company at the date hereof or of any business in which Company is substantially engaged at any time during the term of this Agreement; and

(iii)  shall not induce or attempt to persuade any employee of Company or any of its divisions, subsidiaries or then present affiliates to terminate his or her employment relationship in order to enter into competitive employment.

(b)  Unauthorized Disclosure.    During the period Executive is employed under this Agreement, and for a further period of two years thereafter, Executive shall not, except as required by any court or administrative agency, without the written consent of the Board of Directors, or a person authorized thereby, disclose to any person, other than an employee of Company or a person to whom disclosure is reasonably necessary or appropriate in connection with the performance by Executive of his duties as an executive for Company, any confidential information obtained by him while in the employ of Company; provided, however, that confidential information shall not include any information now known or which becomes known generally to the public (other than as a result of unauthorized disclosure by Executive).

(c)  Scope of Covenants; Remedies.    The following provisions shall apply to the covenants of Executive contained in this Section 8:

(i)  the covenants contained in paragraph (i) and (ii) of Section 8(a) shall apply within all the territories in which Company is actively engaged in the conduct of business while Executive is employed under this Agreement, including,

6

without limitation, the territories in which customers are then being solicited;

(ii)  without limiting the right of Company to pursue all other legal and equitable remedies available for violation by Executive of the covenants contained in this Section 8, it is expressly agreed by Executive and Company that such other remedies cannot fully compensate Company for any such violation and that Company shall be entitled to injunctive relief to prevent any such violation or any continuing violation thereof;

(iii)  each party intends and agrees that if, in any action before any court or agency legally empowered to enforce the covenants contained in this Section 8, any term, restriction, covenant or promise contained therein is found to be unreasonable and accordingly unenforceable, then such term, restriction, covenant or promise shall be deemed modified to the extent necessary to make it enforceable by such court or agency; and

(iv)  the covenants contained in this Section 8 shall survive the conclusion of Executive’s employment by Company.

9.  General Provisions.

(a)  Notices.    Any notice to be given hereunder by either party to the other may be effected by personal delivery, facsimile, electronic mail or U.S. mail, registered or certified, postage prepaid with return receipt requested. Mailed notices shall be addressed to the parties at the addresses set forth below, but each party may change his or its address by written notice in accordance with this Section 9(a). Notices shall be deemed communicated as of the actual receipt or refusal of receipt.

(b)  Partial Invalidity.    If any provision in this Agreement is held by a court of competent jurisdiction to be invalid, void or unenforceable, the remaining provisions shall, nevertheless, continue in full force and without being impaired or invalidated in any way.

7

(c)  Governing Law.    This Agreement shall be governed by and construed in accordance with the laws of the State of Tennessee.

(d)  Entire Agreement.    Except for any prior grants of options, restricted stock, or other forms of incentive compensation evidenced by a written instrument — some of which are attached hereto as Exhibit A — or by an action of the Board or Directors, this Agreement supersedes any and all other agreements, either oral or in writing, between the parties hereto with respect to employment of Executive by Company and contains all of the covenants and agreements between the parties with respect to such employment. Each party to this Agreement acknowledges that no representations, inducements or agreements, oral or otherwise, that have not been embodied herein, and no other agreement, statement or promise not contained in this Agreement, shall be valid or binding. Any modification of this Agreement will be effective only if it is in writing signed by the party to be charged.

(e)  No Conflicting Agreement.    By signing this Agreement, Executive warrants that he is not a party to any restrictive covenant, agreement or contract which limits the performance of his duties and responsibilities under this Agreement or under which such performance would constitute a breach.

(f)  Headings.    The Section, paragraph, and subparagraph headings are for convenience or reference only and shall not define or limit the provisions hereof.

(g)  Attorney’s Fees.    If any case is brought to enforce any right or provision set out in this Agreement, Company shall reimburse Executive for reasonable costs incurred (including attorneys’ fees) by Executive: (i) in the case of termination of employment that occurs prior to a Change in Control only if the Executive substantially prevails, and (ii) in the case of termination of employment after a Change in Control regardless of the outcome of the action with reimbursement being made as expenses are incurred.

8

IN WITNESS WHEREOF, the parties have executed this Agreement as of the date first written above.

R. Brad Martin

Executive

9