SEPARATION AGREEMENT WITH WAIVER AND RELEASE OF CLAIMS

Exhibit 10.1

SEPARATION AGREEMENT WITH WAIVER AND RELEASE OF CLAIMS

This Separation Agreement with Waiver and Release of Claims (the “Agreement”) is entered into as of October 26, 2004, by and between Blockbuster Inc. (“Blockbuster”) and Nigel Travis (“Mr. Travis”) (collectively the “Parties”).

1. Mr. Travis’ employment with Blockbuster is hereby terminated, such termination to be effective as of December 31, 2004, or such earlier date as may be directed by Blockbuster’s Chief Executive Officer (“CEO”). On the date of this Agreement, Mr. Travis hereby resigns from his positions of President, Chief Operating Officer and any other official positions held pursuant to his employment with Blockbuster and from that day forward is an at-will employee and shall perform such duties, if any, as assigned by Blockbuster’s CEO. After the date of his termination, or such earlier date as may be required by law, Mr. Travis shall receive a lump sum payment for any accrued, unused vacation, less ordinary withholding tax, on or before the next regularly scheduled payday, or such earlier date as may be required by law.

2. Mr. Travis’ separation pay and benefits shall consist of the following:

a. Severance Payments. As of the date of this Agreement, Mr. Travis’ Employment Agreement with Blockbuster dated as of October 13, 2000 (as amended to date, the “Employment Agreement”) which Employment Agreement supercedes all other agreements or contracts related to his employment, shall be terminated. In lieu of any rights under the Employment Agreement, Blockbuster shall provide Mr. Travis with severance pay in an amount equal to 12 months of his current base salary commencing on January 1, 2005. The severance pay shall be paid bi-weekly or in accordance with Blockbuster’s then effective payroll practices. In addition, on or about December 31, 2004, Mr. Travis shall receive a lump sum payment of one million dollars ($1,000,000.00), less any applicable withholdings, which payment shall be in lieu of the additional 24 months of mitigated severance payments (including salary, insurance coverage and all other payments contemplated in the Employment Agreement). No payments of any kind other than his salary and benefits excluding stock options through December 31, 2004, and payments specifically enumerated and provided herein shall be due to Mr. Travis pursuant to this Agreement, the Employment Agreement or any other agreements or contracts, including, but not limited to, any payments for calendar years 2006 and 2007.

b. Medical Insurance. Upon termination of his employment with Blockbuster, Mr. Travis shall be entitled to receive medical and dental coverage under COBRA at no cost to him (except as hereafter described) pursuant to Blockbuster’s then current benefit plans. Such coverage shall continue until the earlier of (i) December 31, 2005 or (ii) the date on which Mr. Travis becomes eligible for medical and dental coverage from a third party; provided, that, during the period Blockbuster provides Mr. Travis with this coverage, an amount equal to the applicable COBRA premiums which Mr. Travis would otherwise have to pay for such coverage (or such other amount as required by law) will be included in Mr. Travis’ reported income for tax purposes to the extent required by law. Mr. Travis may elect to continue his medical and dental coverage after December 31, 2005 at his own expense for the balance, if any, of the period required by law.

c. Stock Options. Effective as of the date of this Agreement, Mr. Travis shall surrender any and all stock options granted to him under the Blockbuster Inc. Amended and Restated 1999 Long-Term Management Incentive Plan, as amended to date, or any other Blockbuster plan(s) in exchange for a lump sum payment of one million five hundred thousand dollars ($1,500,000.00), which payment shall be paid on or about December 31, 2004.

d. Bonus Compensation. Mr. Travis shall receive bonus compensation for the 2004 calendar year payable by the end of the first quarter of 2005, as determined pursuant to the terms of the Amended and Restated Senior Executive Short Term Incentive Plan (“SESTIP”) and in accordance with the sole discretion and determination of the Senior Executive Compensation Committee of the Blockbuster Board of Directors. Bonus compensation for the 2005 calendar year shall be paid to Mr. Travis in an amount as solely determined by the Senior

Executive Compensation Committee of the Blockbuster Board of Directors. If other then current Executive Vice Presidents receive bonus payments for the 2004 or 2005 calendar years, Mr. Travis will be eligible to receive bonus payments for the 2004 or 2005 calendar years, respectively. No bonus or other incentive payments shall be paid for any other calendar years.

e. Car Allowance. Mr. Travis shall continue to receive his car allowance of seven hundred fifty dollars ($750.00) per month and car insurance until December 31, 2005 paid in accordance with Blockbuster’s then effective payroll practices.

f. Life Insurance. Mr. Travis shall be entitled to life insurance coverage in an amount equal to two times his annual salary under Blockbuster’s United States (“US”) life insurance plan and in an amount equal to two times his annual salary under Blockbuster’s United Kingdom (“UK”) life assurance plan until December 31, 2005 at no cost to him.

g. UK Travel Reimbursement. Mr. Travis and his dependents living with him in the United States shall be reimbursed for one trip to the UK to commence in December 2004. The reimbursement shall include business-class airfare to and from the UK. Meals and other incidentals are not included. No other expenses for personal travel shall be reimbursed.

3. In consideration for this Agreement by Blockbuster to provide Mr. Travis with the separation package outlined herein, the sufficiency of which Mr. Travis acknowledges, Mr. Travis, on behalf of himself, his successors, heirs, and assigns, releases and forever discharges Blockbuster and its subsidiaries, parent and affiliated companies, employees, officers and directors, and their respective assigns from any and all manner of claims, debts, demands, damages, liabilities and causes of action, whether known or unknown from the beginning of time, which Mr. Travis, his successors, heirs, and assigns, may have had or may presently have, relating to or arising out of the employment relationship or the termination of said relationship including, but not limited to causes of action for libel, slander, breach of contract, impairment of economic opportunity, intentional infliction of emotional distress or any other tort, or claims under federal, state, or local constitutions, statutes, regulations, ordinances or common law, including, but not limited to, the Employee Retirement Income Security Act of 1974, the Civil Rights Acts of 1866, 1871, 1964 and 1991, the Age Discrimination in Employment Act, as amended by the Older Workers Benefit Protection Act of 1990, the Equal Pay Act of 1963, the Americans with Disabilities Act of 1990, the Texas Commission on Human Rights Act, and the Family and Medical Leave Act of 1993. You understand that you are not waiving any right under the Older Workers Benefit Protection Act to test the knowing and voluntary nature of this Agreement in court. Mr. Travis further agrees on behalf of himself, his successors, heirs, and assigns, to release and forever discharge Blockbuster and its subsidiaries, parent and affiliated companies, employees, officers and directors, and their respective assigns, from all claims pursuant to the laws of the United Kingdom, including but not limited to, any claim in relation to wages under part II of the Employment Rights Act of 1996, any claim in relation to a redundancy payment under part XI of the Employment Rights Act of 1996, any claim for unfair dismissal under the Employment Rights Act of 1996, any claim under the Sex Discrimination Act of 1975, any claim under the Race Relations Act of 1976, any claim under the Equal Pay Act of 1970, any claim under the Trade Union and Labour Relations (Consolidation) Act of 1992, any claim under the Disability Discrimination Act of 1995, any claim under the Public Interest Disclosure Act of 1998, any claim under the Working Time Regulations of 1998, and any claim under Article 119 of the Treaty of Rome. He agrees to refrain from instituting or continuing any such Tribunal or Court claims against Blockbuster. For the avoidance of doubt, such claims are to be treated as “particular proceedings” within the terms of Section 203(3) (b) of the Employment Rights Act 1996 and “particular complaints” for the purposes of s.72 (4A) (b) of the Race Relations Act 1976 and S77 (4A) (b) of the Sex Discrimination Act 1975 (together referred to as the Acts, which expression shall include all Regulations made under them and all modifications or amendments). He further agrees that the compensation paid to him pursuant to this agreement includes any sum which might have been payable in respect of the basic award and the compensatory award and includes any sum which might have been payable in respect of contractual damages, in the event that, notwithstanding any provision in this agreement, he were found to have been unfairly or wrongfully dismissed. Mr. Travis agrees that it would not be just or equitable for a Court or Employment Tribunal to grant any further award or compensation to him in respect of such claims.

4. In addition to those terms and conditions previously stated herein, this Agreement is subject to the following terms and conditions:

a. Blockbuster shall not be obligated to provide Mr. Travis with any other compensation or benefits other than those enumerated herein.

b. Nothing contained in this Agreement constitutes an admission of liability by Blockbuster concerning any aspect of this employment relationship or the termination of said relationship.

c. Unless specified in this Agreement to the contrary, participation in all Blockbuster benefit plans and programs (including, without limitation, vacation accrual, the United Kingdom pension plan, Long and Short Term Disability plans, accidental death and dismemberment and business travel and accident insurance) will end upon termination of Mr. Travis’ employment subject to any vested rights he may have under the terms of such plans or programs. Mr. Travis understands that he will not accrue any additional benefits or employment rights other than those specifically referenced herein.

d. Mr. Travis does not waive any rights or claims that may arise after the date this Agreement is executed, except that Mr. Travis agrees and acknowledges that upon execution of this agreement he becomes an at-will employee of Blockbuster and understands that his employment will terminate no later than December 31, 2004. This provision is intended to include any claims that may have arisen before the date of this Agreement but which are unknown to Mr. Travis as of the date of this Agreement.

e. The consideration given by Blockbuster under this Agreement is intended to resolve any potential claim arising out of the employment relationship or the termination of said relationship and in excess of any sums he might otherwise be entitled to receive without having entered into this Agreement. These sums are a substitute for any and all compensation and benefits Mr. Travis would have received had this Agreement not been executed.

f. Subject to reimbursement of reasonable out-of-pocket travel costs and expenses, Mr. Travis agrees to cooperate fully with Blockbuster and its counsel with respect to any matter (including litigation, investigation or governmental proceeding) which relates to matters with which Mr. Travis was involved or for which he has or had knowledge during his employment with Blockbuster. Such cooperation shall include appearing from time to time at the offices of Blockbuster or Blockbuster’s counsel for conferences and interviews, providing sworn testimony in any form, and in general providing the officers of Blockbuster and its counsel with the full benefit of Mr. Travis’ knowledge with respect to any such matter. Mr. Travis agrees to render such cooperation in a timely fashion and at such times as may be mutually agreeable to the parties concerned.

g. Mr. Travis agrees that, during the pendency of any litigation or other proceeding, and anytime thereafter, he will not communicate with anyone (other than his attorneys or tax advisors) with respect to the facts or subject matter of any pending or potential litigation, or regulatory or administrative proceeding involving Blockbuster, including any of its affiliates, or any of its officers, directors, agents, employees, suppliers or customers, other than any litigation or other proceeding in which Mr. Travis is a party-in-opposition, without giving prior notice to Blockbuster’s General Counsel, and in the event that any other party attempts to obtain information or documents from Mr. Travis with respect to matters possibly related to such litigation or other proceeding, Mr. Travis will promptly so notify Blockbuster’s General Counsel and not discuss such matter with any other party without prior consultation with Blockbuster’s General Counsel.

h. Mr. Travis acknowledges that, during the course of the employment relationship, he has or will become privy to confidential and proprietary business information belonging to Blockbuster, the unauthorized disclosure of which could cause serious and irreparable injury to Blockbuster and its affiliates. The information includes, but is not limited to, information concerning existing and prospective expansion plans; existing and potential financing sources and arrangements; existing and prospective marketing plans and activities; proprietary computer software programs and applications; existing and prospective franchise plans; existing and prospective Internet-related plans; business plans and strategies and other non-public information. Mr. Travis agrees to hold and safeguard the confidential information in trust for Blockbuster, its successors and assigns, and

agrees that he will not misappropriate, use for his own advantage, disclose or otherwise make available to anyone who is not an officer of Blockbuster, for any reason, any of the confidential information, regardless of whether the confidential information was developed or prepared by him or others. Mr. Travis agrees not to remove any writings containing confidential information, or copies or summaries of same, from Blockbuster’s premises or possession without Blockbuster’s express consent. Mr. Travis agrees to promptly return to Blockbuster all confidential information in Mr. Travis’ possession or under Mr. Travis’ control (whether in original, copy, or electronic form). Before disclosing any confidential information under compulsion of legal process, Mr. Travis agrees to promptly give notice to Blockbuster of the fact that he has been served with legal process pursuant to which the disclosure of confidential information may be requested. Such notice will be given within sufficient time to permit Blockbuster to intervene in the matter or to take such other actions as may be necessary or appropriate to protect its interest. The scope of this Agreement is not limited to information that is patented, patentable, copyrighted or technically classifiable as a trade secret. This provision is intended to survive the termination of Mr. Travis’ employment.

i. Mr. Travis will not, prior to March 1, 2007, directly or indirectly engage in or participate as an officer, director, agent, employee, or consultant of any business that competes with Blockbuster, nor shall Mr. Travis make any investments in any company or business that competes with Blockbuster by providing home entertainment, including movies and games, to consumers via any means whether now or hereafter developed; provided, however, that nothing herein shall prevent Mr. Travis from investing as less than a one (1%) percent shareholder in the securities of any company listed on a national exchange or quoted on an automated quotation system. Mr. Travis agrees that the determination regarding whether a conflict exists pursuant to this paragraph will be made by Blockbuster’s CEO.

j. Mr. Travis will not, prior to March 1, 2007, directly or indirectly, call upon, solicit, divert or take away, or attempt to solicit, divert or take away, any customers or clients Mr. Travis became acquainted with as a result of his employment with Blockbuster

k. As a material inducement to Blockbuster to enter into this Agreement, Mr. Travis agrees not to make, write or publish, or assist, participate or collaborate in the making, writing or publishing of, any disparaging oral or written statement, including but not limited to, any book, article or other publication, now, or at any time in the future, to representatives of any media, any other person, or the public, regarding or in any way relating, directly or indirectly, to Mr. Travis’ employment with Blockbuster or the business, reputation, competence or character of Blockbuster or any officer, director, employee, partner, joint venturer, franchisee or licensee of Blockbuster.

l. Mr. Travis will not, prior to March 1, 2007, hire, attempt to hire, or be involved with hiring, directly or indirectly, any Blockbuster employee away from Blockbuster. In addition, Mr. Travis agrees not to encourage or induce any Blockbuster employee to leave Blockbuster.

m. Mr. Travis shall return all company property to Blockbuster on or before his last date of employment.

n. For breach of any provision of this Agreement, the parties shall have such remedies and rights as are customarily available at law or in equity, except that, in any action or proceeding brought to enforce this Agreement or to recover damages for its breach, the prevailing party shall be entitled to recover, should it substantially prevail in the matter, reasonable attorneys’ fees and litigation expenses.

o. In the event Mr. Travis, his heirs or assigns or any party acting on behalf of Mr. Travis, contests, violates or breaches this Agreement, Blockbuster’s obligations imposed herein shall be extinguished and Blockbuster shall not be obligated to continue performance under this Agreement. In such a case, Mr. Travis shall be required to re-pay Blockbuster all consideration received pursuant to this Agreement and this Agreement will act as a complete and total bar to any recovery by Mr. Travis. This provision does not apply to a challenge asserting a breach of this Agreement by Blockbuster.

p. Mr. Travis agrees that the legal remedies for the breach of this Agreement would not be adequate, and that, in addition to any other remedies available at law, these provisions may be specifically enforced by temporary or permanent injunctive or other equitable relief.

q. In the event of Mr. Travis’ death while his he is still entitled to receive compensation under this Agreement, his beneficiary or estate will receive, to the extent permitted by law, any compensation or other benefits contemplated herein but not yet paid.

r. THIS AGREEMENT SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF TEXAS, IRRESPECTIVE OF THE CONFLICT OF LAWS RULES. FURTHERMORE, BLOCKBUSTER AND MR. TRAVIS AGREE THAT THE TEXAS COURTS ARE THE EXCLUSIVE FORUM FOR RESOLVING ANY DISPUTES ARISING OUT OF THIS AGREEMENT OR MR. TRAVIS’ EMPLOYMENT.

s. Mr. Travis has been advised to discuss this Agreement with an attorney of his choice before signing it, and is freely and voluntarily signing this document in exchange for the promises and consideration provided by Blockbuster under this Agreement.

t. This Agreement will supersede all prior written or oral agreements or understandings between Blockbuster and Mr. Travis relating to his employment by and separation from Blockbuster including the Employment Agreement and any other agreements or contracts. This Agreement represents the full understanding between Mr. Travis and Blockbuster, and no parol evidence shall be relevant to supplement or explain this Agreement.

u. Should any provision of this Agreement be found unenforceable, the remainder of the Agreement, in its modified form, shall nonetheless be fully enforceable.

v. Mr. Travis acknowledges that he has been given at least twenty-one (21) days to review consider this Agreement and may revoke acceptance within seven (7) days of the execution of this Agreement. Pursuant to the Age Discrimination in Employment Act, as amended by the Older Workers Benefit Protection Act of 1990, this Agreement shall become effective and enforceable immediately upon the expiration of the revocation period so long as Mr. Travis has not executed his right of revocation.

IN WITNESS WHEREOF, we hereunto set our hands, this 26^th day of October, 2004.

DATE: October 26, 2004

BLOCKBUSTER INC.

DATE: October 26, 2004