VIACOM INC. and BLOCKBUSTER INC.

Exhibit 10.4

Execution Copy

AMENDED AND RESTATED

TRANSITION SERVICES AGREEMENT

BETWEEN

VIACOM INC.

and

BLOCKBUSTER INC.

Dated as of

JUNE 18, 2004

TABLE OF CONTENTS

AMENDED AND RESTATED TRANSITION SERVICES AGREEMENT

AMENDED AND RESTATED TRANSITION SERVICES AGREEMENT (this “Agreement”), dated as of June 18, 2004, to be effective for all purposes as provided in Section 6.07, between VIACOM INC., a Delaware corporation (“Parent”) and BLOCKBUSTER INC., a Delaware corporation (the “Company”).

RECITALS

WHEREAS, Parent, pursuant to the transactions contemplated by the registration statement of the Company filed on Form S-4 with the Securities and Exchange Commission on the date hereof, intends to split-off the Company in a tax-free transaction;

WHEREAS, Parent has heretofore provided certain services to the Company pursuant to the Transition Services Agreement between Parent and the Company, dated as of August 16, 1999 (the “Original Agreement”); and

WHEREAS, the Company has requested from Parent that Parent continue to provide certain of such services to the Company, along with certain additional services, for a limited period of time after the Effective Time (defined below), pursuant to the terms and conditions set forth in this Agreement.

NOW THEREFORE, in consideration of the above premises and the representations, warranties, covenants and agreements contained herein, it is agreed by and between the parties as follows:

Capitalized terms not otherwise defined herein have the meaning given to them in the Amended and Restated Initial Public Offering and Split-Off Agreement dated as of the date hereof among Viacom, Viacom International Inc. and Blockbuster (the “IPO Agreement”).

ARTICLE I

SERVICES

Section 1.01. Provision of Services. As used in this Agreement, “Effective Time” means the earlier to occur of (x) the first day after the closing of any exchange offer by Parent pursuant to an effective Form S-4 prospectus-offer to exchange stock of the Company for stock of Parent, as filed with the Securities and Exchange Commission and (y) the Split-Off Date. Subject to the terms and conditions of this Agreement and in accordance with the standards of performance set forth in Section 1.02, as of the Effective Time, Parent shall provide or cause to be provided to the Company (which term, for purposes of this Article I will be deemed to include its Subsidiaries) the following transition services (the “Services”) during the Term (as hereinafter defined):

1

(a) Audit and Control Services. Parent shall provide or cause to be provided to the Company certain audit and control services for its domestic and international operations, consistent with past practice. With respect to any audit or control projects which Parent internal audit staff is actively working on and which are in process as of the Effective Time, Parent and the Company will cooperate with each other to cause such projects to be delivered to the Company in final form on or prior to the Termination Date. No such projects shall commence after the date that is 30 days prior to the Company’s and Parent’s reasonable estimate of the date on which the Effective Time will occur.

(b) Employee Benefit Plans and Insurance Administration. Parent shall assist the Company in the administration of all employee benefit plans and policies of insurance covering employees of the Company and its Affiliates, consistent with past practice.

(c) Intellectual Property Services. Parent shall provide or cause to be provided to the Company certain intellectual property services, consistent with past practice.

(d) Legal Services. Parent shall provide or cause to be provided to the Company certain legal services, consistent with past practice.

(e) Tax Services. Parent shall provide or cause to be provided to the Company certain tax services, consistent with past practice and in compliance with the Tax Matters Agreement.

Section 1.02. Standard of Performance. (a) Parent agrees to provide or cause to be provided to the Company the Services in substantially the same manner and at substantially the same levels as such Services were provided to the Company prior to the Effective Time. Notwithstanding anything to the contrary in this Agreement, Parent shall not provide any particular services if requested by the Company not to do so, provided that no such request shall affect the amount of the Services Fee or payment thereof.

(b) Notwithstanding the foregoing, in providing the Services, Parent shall not be obligated to (i) hire any additional employees, (ii) maintain the employment of any specific employee or (iii) purchase, lease or license any additional equipment.

ARTICLE II

FEES, TERM AND TERMINATION

Section 2.01. Fee and Payment. (a) As consideration for the Services to be provided to the Company and its Subsidiaries by Parent under the terms of this Agreement, the Company shall pay to Parent a services fee of $150,000 per month during

2

the Term (the “Services Fee”). The Services Fee only represents payment with respect to Parent’s provision of the Services and not for other payments, costs or expenses related to the underlying Services themselves. The Services Fee shall be payable by the Company to Parent fifteen (15) days after the last day of each month (prorated for any partial month) during the Term. The final payment of the Services Fee shall be made to Parent not later than fifteen (15) days after the last day of the month during which the Termination Date occurs.

(b) Parent shall invoice the Company for any out-of-pocket payments, costs or expenses incurred in good faith associated with, or related to, the underlying Services provided by Parent hereunder and the Company shall promptly (and, in any event, within thirty (30) days after the Company’s receipt of the invoice) pay or reimburse Parent for any such payments, costs or expenses, provided that the categories of such payments, costs or expenses for which payment or reimbursement is required will be consistent with those charged to the Company in past practice under this Agreement prior to the Effective Time. Such payments and reimbursements shall be separate from and in addition to the Services Fee.

Section 2.02. Term for Provision of Services. The term during which Services shall be provided hereunder (the “Term”) shall commence at the Effective Time and shall expire on the date which is ninety (90) days from the Effective Time (the “Termination Date”).

ARTICLE III

COOPERATION, ACCESS AND AUDIT

Section 3.01. Cooperation; Access; Audit.

(a) Each of the parties hereto agrees to fully cooperate in good faith with the others in connection with the Services provided under this Agreement and matters related to or arising hereunder.

(b) For purposes of verifying the accuracy of charges for Services rendered hereunder and to verify the proper performance of Services by Parent, the Company shall be entitled to have reasonable access during regular business hours, during the period extending from the Effective Time until 60 days after the Termination Date, upon reasonable prior notice, to (i) such premises of Parent that are being used in the provision of Services hereunder, (ii) such records of Parent that relate primarily to the provision of Services hereunder and (iii) any agent of Parent providing the Services hereunder (including any individual responsible for such records or for providing the Services), subject to any access or other requirements of such agent.

3

ARTICLE IV

DISPUTE RESOLUTION

Section 4.01. Dispute Resolution. In the event any dispute arises under this Agreement, the parties hereto agree to negotiate in good faith to resolve such dispute prior to seeking relief in a court of law in accordance with Section 6.10. Any party may at any time deliver a notice to any other party that it wishes to refer a dispute to a senior executive of Parent and a senior executive of the Company. Following receipt of such notice each party shall designate one of its senior executives to negotiate in good faith to resolve such dispute within ten (10) days (or such longer period of time as such officers may agree to in writing). If at the end of such ten (10) day (or longer if properly extended) period the designated officers have not fully resolved the dispute to their mutual satisfaction, either party may thereafter seek relief in a court of law in accordance with Section 6.10.

ARTICLE V

LIMITATION OF LIABILITY AND INDEMNIFICATION

Section 5.01. Limitation of Liability. (a) Parent shall not have any duties or responsibilities hereunder other than those specifically set forth herein and no implied obligations shall be read into this Agreement.

(b) In the absence of gross negligence or reckless or willful misconduct on Parent’s part, and whether or not it is negligent, Parent and its Affiliates shall not be liable for any Losses (as hereinafter defined) whatsoever in providing or failing to provide the Services to the Company. No party hereto shall be liable to any other for any special, indirect, punitive, incidental or consequential damages of the other arising in connection with this Agreement.

(c) Parent’s and its Affiliates’ liability for damages to the Company and its Affiliates for any cause whatsoever, and regardless of the form of action, whether in contract or in tort, including gross negligence or willful misconduct, shall be limited to the Services Fee.

Section 5.02. Indemnity by the Company. The Company shall indemnify and hold harmless Parent against all claims, liabilities, damages, losses, costs, expenses (including, but not limited to, settlements, judgments, court costs and attorneys’ fees, including attorneys’ fees incurred in enforcing this obligation) and all losses and damages of any nature whatsoever (“Losses”) as incurred, arising out of or relating to the Services,

4

except for Losses which are the direct and sole result of gross negligence or reckless or willful misconduct of the personnel of Parent.

Section 5.03. Indemnification Procedures. The indemnification procedures set forth in Section 8.01(b) of the IPO Agreement are incorporated herein and made a part hereof for all purposes as if fully set forth herein and shall govern the parties’ rights and obligations with respect thereto.

ARTICLE VI

MISCELLANEOUS

Section 6.01. Relationship of the Parties. It is expressly understood and agreed that in rendering the Services hereunder, Parent is acting as an independent contractor and that this Agreement does not constitute Parent as an employee, agent or other representative of the Company for any purpose whatsoever. Parent does not have the right or authority to enter into any contract, warranty, guarantee or other undertaking in the name or for the account of the Company, or to assume or create any obligation or liability of any kind, express or implied, on behalf of the Company, or to bind the Company in any manner whatsoever, or to hold itself out as having any right, power or authority to create any such obligation or liability on behalf of the Company or to bind the Company in any manner whatsoever (except as to any actions taken by Parent at the express written request and direction of the Company).

Section 6.02. Force Majeure. In the event that Parent is prevented from performing, or is unable to perform, any of its obligations under this Agreement due to any act of God, fire, casualty, flood, war, terrorism, strike, lock out, failure of public utilities, injunction or any act, exercise, assertion or requirement of governmental authority, epidemic, destruction of production facilities, insurrection, inability to procure goods, materials, services, labor, equipment, transportation or energy sufficient to meet manufacturing needs, or any other cause beyond the reasonable control of Parent, and if Parent shall have used its commercially reasonable efforts to avoid such occurrence and minimize its duration, then Parent’s performance for the period of delay or inability to perform due to such occurrence shall be suspended. To the extent practicable, Parent shall provide proper notice to the Company that it is unable to perform on account of one or more reasons set forth in this section. Should Parent fail to perform hereunder on account of one or more reasons set forth in this section, the Company may obtain replacement services from a third party for the duration of such delay or inability to perform, or for such longer period as the Company shall be reasonably required to commit to in order to obtain such replacement services and the Services Fee shall be reduced accordingly.

Section 6.03. Confidentiality. Without limiting any rights or obligations under any other agreement between or among the parties hereto and/or any of their respective Affiliates relating to confidentiality, each of the parties hereto agrees that

5

it shall be bound by the confidentiality provisions of Article IV of the IPO Agreement, the terms of which are incorporated herein and made a part hereof for all purposes as if fully set forth herein and shall govern the parties’ rights and obligations with respect thereto.

Section 6.04. Amendments. This Agreement shall not be supplemented, amended or modified in any manner whatsoever (including without limitation by course of dealing or of performance or usage of trade) except in writing signed by the parties.

Section 6.05. Successors and Assignment. This Agreement shall be binding upon and inure to the benefit of the parties and their respective successors and permitted assigns. This Agreement may not be assigned by any party by operation of law or otherwise without the express written consent of the other parties (which consent may be granted or withheld by such parties in their sole discretion).

Section 6.06. Severability. Whenever possible, each provision of this Agreement shall be interpreted in such a manner as to be effective and valid under applicable law. If any portion of this Agreement is declared invalid for any reason in any jurisdiction, such declaration shall have no effect upon the remaining portions of this Agreement, which shall continue in full force and effect as if this Agreement had been executed with the invalid portions thereof deleted; provided that the entirety of this Agreement shall continue in full force and effect in all other jurisdictions and; provided further, that the parties shall negotiate in good faith toward a replacement for such provision that is valid and enforceable and substantially approximates the parties’ intent and the economic benefits to be derived from the invalid provision.

Section 6.07. Entire Agreement. As of the Effective Time, the Original Agreement is hereby terminated and is void and of no effect, and this Agreement and the Ancillary Agreements constitute the entire agreement of the parties hereto with respect to the subject matter hereof and thereof and supersede all prior agreements and undertakings, both written and oral, between the parties with respect to the subject matter hereof and thereof; provided however that the Original Agreement shall continue to govern, and be binding on the parties hereto or their respective successors or permitted assigns, with respect to any period prior to the Effective Time.

Section 6.08. Headings. The heading references herein and the table of contents hereto are inserted for convenience of reference only, do not constitute a part of this Agreement and shall not be deemed to limit or affect any of the provisions hereof.

Section 6.09. Notices. All notices, consents, requests, approvals, and other communications provided for or required herein, and all legal process in regard thereto, must be in writing and shall be deemed validly given, made or served, (a) when delivered personally or sent by telecopy to the facsimile number indicated below with a required confirmation copy sent in accordance with subsection (c) below; or (b) on the next business day after delivery to a nationally recognized express delivery service with instructions and payment for overnight delivery; or (c) on the fifth (5^th) day after deposited in any depository regularly maintained by the United States postal service,

6

postage prepaid, certified or registered mail, return receipt requested, addressed to the following addresses or to such other address as the party to be notified shall have specified to the other party in accordance with this section:

If to Parent:

1515 Broadway

New York, New York 10036

Attention: General Counsel

Phone Number: 212 ###-###-####

Fax Number: 212 ###-###-####

If to the Company:

1201 Elm Street

Dallas, Texas 75270

Attention: General Counsel

Phone Number: 214 ###-###-####

Fax Number: 214 ###-###-####

Section 6.10. Governing Law. This Agreement shall be governed by and construed in accordance with the laws of the State of New York. Subject to Section 4.01 above, each of the parties hereto agrees that any dispute relating to or arising from this Agreement or the transactions contemplated hereby shall be resolved only in the Court of the State of New York sitting in the County of New York or the United States District Court for the Southern District of New York and the appellate courts having jurisdiction of appeals in such courts. In that context, and without limiting the generality of the foregoing, each of the parties hereby irrevocably and unconditionally:

(a) submits for itself and its property in any legal suit, action or proceeding relating to this Agreement or transaction contemplated hereby, or for recognition and enforcement of any judgment in respect thereof, to the exclusive jurisdiction of the Courts of the State of New York sitting in the County of New York or the United States District Court for the Southern District of New York and appellate courts having jurisdiction of appeals in such courts, and each of the parties hereto irrevocably and unconditionally agrees that all claims in respect of any such suit, action, or proceeding shall be heard and determined in such New York State court or, to the extent permitted by law, in such federal court;

(b) consents that any such suit, action or proceeding may and shall be brought in such courts and waives any objection that it may now or hereafter have to the venue or jurisdiction or any such action or proceeding in such court or that such action or proceeding was brought in an inconvenient forum and agrees not to plead or claim the same;

7

(c) agrees that service of process in any such action or proceeding may be effected by mailing a copy thereof registered or certified mail (or any substantially similar form of mail), postage prepaid, to such party in its address as provided in Section 6.09 hereof;

(d) agrees that nothing herein shall affect the right to effect service of process in any other manner permitted by New York law; and

(e) agrees that this Agreement has been entered into in the State of New York and performed in part in the State of New York.

Section 6.11. Counterparts. This Agreement may be executed in separate counterparts (including by facsimile), each of which shall be deemed an original, and all of which shall constitute one and the same instrument.

8

IN WITNESS WHEREOF, the parties have caused this Agreement to be executed as of the date first written above by their respective officers thereunto duly authorized.

9