NEW COMMON STOCK WARRANT AGREEMENT

Exhibit 4.1

NEW COMMON STOCK WARRANT AGREEMENT

(New Common Stock Warrants)

by and between

MOVIE GALLERY, INC.,

and

American Stock Transfer and Trust Company,

as Warrant Agent

Dated as of May 20, 2008

SERIES A WARRANT AGREEMENT

TABLE OF CONTENTS ¹

i

ii

SERIES A WARRANT AGREEMENT (this “Warrant Agreement” ), entered into on May 20, 2008, between MOVIE GALLERY, INC., a Delaware corporation (the “Company” ), and American Stock Transfer and Trust Company as Warrant Agent (the “Warrant Agent” ).

WHEREAS, pursuant to the terms and conditions of the restructuring contemplated under the Second Amended Joint Plan of Reorganization of Movie Gallery, Inc. and Its Debtor Subsidiaries Under Chapter 11 of the Bankruptcy Code (the “Bankruptcy Code” ) filed on February 18, 2008 (as may be amended from time to time, the “Plan” ), the holders of certain Allowed Claims (as defined in the Plan) are to be issued Warrants (the “Warrants” ) exercisable until the Expiration Date (as defined below), to purchase up to 3,000,000 shares of common stock, par value $0.001 per share, of the Company ( “New Common Stock” ) at an exercise price of $20.00 per share of New Common Stock, as adjusted pursuant to Section 12 hereof (the “Exercise Price” );

WHEREAS, the Warrants are being issued pursuant to, and upon the terms and conditions set forth in, the Plan in an offering in reliance on the exemption afforded by section 1145 of the Bankruptcy Code from the registration requirements of the Securities Act of 1933, as amended (the “Securities Act” ), and of any applicable state securities or “ blue sky ” laws;

WHEREAS, the Company desires the Warrant Agent to act on behalf of the Company, and the Warrant Agent is willing so to act, in connection with the issuance of Warrant certificates and other matters as provided herein; and

WHEREAS, for purposes of this Warrant Agreement, “person” shall be interpreted broadly to include an individual, corporation, partnership, joint venture, association, joint stock company, limited liability company, limited liability partnership, national banking association, trust, trustee, estate, unincorporated organization, government, governmental unit, agency, or political subdivision thereof, or other entity.

NOW, THEREFORE, in consideration of the premises and the mutual agreements herein set forth, the parties hereto agree as follows:

SECTION 1. Appointment of Warrant Agent . The Company hereby appoints the Warrant Agent to act as warrant agent for the Company in accordance with the express (and no implied) instructions set forth hereinafter in this Warrant Agreement, and the Warrant Agent hereby accepts such appointment.

SECTION 2. Issuance of Warrants . In accordance with Section 5 hereof and the Plan, the Company will cause to be issued to the Depository (as defined below), one or more Global Warrant Certificates (as defined below) evidencing a portion of the Warrants. The remainder of the Warrants shall be issued by book-entry registration on the books of the Warrant Agent ( “Book-Entry Warrants” ) and shall be evidenced by statements issued by the Warrant Agent from time to time to the registered holder of book-entry Warrants reflecting such book-entry position (the “Warrant Statement” ). Each Warrant evidenced thereby entitles the holder, upon proper exercise and payment of the applicable Exercise Price, to receive from the Company, as adjusted as provided herein, one share of New Common Stock at the Exercise Price. The shares of New Common Stock or (as provided pursuant to Section 12 hereof) other shares of capital

stock deliverable upon proper exercise of the Warrants are referred to herein as the “Warrant Shares . ” The words “holders” or “holder , ” as used herein in respect of any Warrants or Warrant Shares, shall mean the registered holder or registered holders thereof.

SECTION 3. Warrant Certificates . Subject to Section 6 of this Agreement, the Warrants shall be issued (1) via book-entry registration on the books and records of the Warrant Agent and evidenced by the Warrant Statements, in substantially the form set forth in Exhibit A attached hereto, and/or (2) in the form of one or more global certificates (the “Global Warrant Certificates” ), the forms of election to exercise and of assignment to be printed on the reverse thereof, in substantially the form set forth in Exhibit B attached hereto. The Warrant Statements and Global Warrant Certificates may bear such appropriate insertions, omissions, substitutions and other variations as are required or permitted by this Warrant Agreement, and may have such letters, numbers or other marks of identification and such legends or endorsements placed thereon as may be required to comply with any law or with any rules made pursuant thereto or with any rules of any securities exchange or as may, consistently herewith, be determined by (i) in the case of Global Warrant Certificates, the Appropriate Officers (as hereinafter defined) executing such Global Warrant Certificates, as evidenced by their execution of the Global Warrant Certificates, or (ii) in the case of a Warrant Statement, any Appropriate Officer, and all of which shall be reasonably acceptable to the Warrant Agent. The Global Warrant Certificates shall be deposited on or after the date hereof with, or with the Warrant Agent as custodian for, The Depository Trust Company (the “Depository” ) and registered in the name of Cede & Co., as the Depository’s nominee. Each Global Warrant Certificate shall represent such number of the outstanding Warrants as specified therein, and each shall provide that it shall represent the aggregate amount of outstanding Warrants from time to time endorsed thereon and that the aggregate amount of outstanding Warrants represented thereby may from time to time be reduced or increased, as appropriate, in accordance with the terms of this Warrant Agreement.

SECTION 4. Execution of Warrant Certificates . Global Warrant Certificates shall be signed on behalf of the Company by its Chairman of the Board, its Chief Executive Officer, or any Vice President, and by the Secretary or any Assistant Secretary (each, an “Appropriate Officer” ). Each such signature upon the Global Warrant Certificates may be in the form of a facsimile signature of any such Appropriate Officer and may be imprinted or otherwise reproduced on the Global Warrant Certificates and for that purpose the Company may adopt and use the facsimile signature of any Appropriate Officer who shall have been an Appropriate Officer at the time of entering into this Warrant Agreement. If any Appropriate Officer who shall have signed any of the Global Warrant Certificates shall cease to be such Appropriate Officer before the Global Warrant Certificates so signed shall have been countersigned by the Warrant Agent or disposed of by the Company, such Global Warrant Certificates nevertheless may be countersigned and delivered or disposed of as though such Appropriate Officer had not ceased to be such Appropriate Officer of the Company; and any Global Warrant Certificate may be signed on behalf of the Company by any person who, at the actual date of the execution of such Global Warrant Certificate, shall be a proper Appropriate Officer of the Company to sign such Global Warrant Certificate, although at the date of the execution of this Warrant Agreement any such person was not such Appropriate Officer.

Global Warrant Certificates shall be dated the date of countersignature by the Warrant Agent and shall represent one or more whole Warrants.

2

SECTION 5. Registration and Countersignature . The Warrant Agent, on behalf of the Company, shall (i) register in the Warrant Register (as defined below) the Book-Entry Warrants and (ii) upon receipt of the Global Warrant Certificates duly executed on behalf of the Company, countersign one or more Global Warrant Certificates evidencing Warrants and shall deliver such Global Warrant Certificates to or upon the written order of the Company. Such written order of the Company shall specifically state the number of Warrants that are to be issued as Book-Entry Warrants and the number of Warrants that are to be issued as a Global Warrant Certificate. A Global Warrant Certificate shall be, and shall remain, subject to the provisions of this Warrant Agreement until such time as all of the Warrants evidenced thereby shall have been duly exercised or shall have expired or been canceled in accordance with the terms hereof. Each holder of Warrants shall be bound by all of the terms and provisions of the Warrant Agreement (a copy of which is available on request to the Secretary of the Company) and any amendments thereto as fully and effectively as if such holder had signed the same.

No Global Warrant Certificate shall be valid for any purpose, and no Warrant evidenced thereby shall be exercisable, until such Global Warrant Certificate has been countersigned by the manual signature of the Warrant Agent. Such signature by the Warrant Agent upon any Global Warrant Certificate executed by the Company shall be conclusive evidence that such Global Warrant Certificate so countersigned has been duly issued hereunder.

The Warrant Agent shall keep, at an office designated for such purpose, books (the “Warrant Register” ) in which, subject to such reasonable regulations as it may prescribe, it shall register the Book-Entry Warrants as well as any Global Warrant Certificates and exchanges and transfers of outstanding Warrants in accordance with the procedures set forth in Section 6 of this Warrant Agreement, all in form satisfactory to the Company and the Warrant Agent. No service charge shall be made for any exchange or registration of transfer of the Warrants, but the Company may require payment of a sum sufficient to cover any stamp or other tax or other governmental charge that may be imposed on the holder of the Warrant in connection with any such exchange or registration of transfer. The Warrant Agent shall have no obligation to effect an exchange or register a transfer unless and until any payments required by the immediately preceding sentence have been made.

Prior to due presentment for registration of transfer or exchange of any Warrant in accordance with the procedures set forth in this Warrant Agreement, the Warrant Agent and the Company may deem and treat the person in whose name any Warrant is registered as the absolute owner of such Warrant (notwithstanding any notation of ownership or other writing made in a Global Warrant Certificate by anyone), for the purpose of any exercise thereof, any distribution to the holder of the Warrant thereof and for all other purposes, and neither the Warrant Agent nor the Company shall be affected by notice to the contrary.

SECTION 6. Registration of Transfers and Exchanges .

(a) Transfer and Exchange of Global Warrant Certificates or Beneficial Interests Therein . The transfer and exchange of Global Warrant Certificates or beneficial interests therein shall be effected through the Depository, in accordance with this Warrant Agreement and the procedures of the Depository therefor.

3

(b) Exchange of a Beneficial Interest in a Global Warrant Certificate for a Book Entry Warrants .

(i) Any holder of a beneficial interest in a Global Warrant Certificate may, upon request, exchange such beneficial interest for a Book-Entry Warrant. Upon receipt by the Warrant Agent from the Depository or its nominee of written instructions or such other form of instructions as is customary for the Depository on behalf of any person having a beneficial interest in a Global Warrant Certificate, the Warrant Agent shall cause, in accordance with the standing instructions and procedures existing between the Depository and Warrant Agent, the number of Warrants represented by the Global Warrant Certificate to be reduced by the number of Warrants to be represented by the Book-Entry Warrants to be issued in exchange for the beneficial interest of such person in the Global Warrant Certificate and, following such reduction, the Warrant Agent shall register in the name of the holder a Book-Entry Warrant and deliver to said Warrant holder a Warrant Statement.

(ii) Book-Entry Warrants issued in exchange for a beneficial interest in a Global Warrant Certificate pursuant to this Section 6(b) shall be registered in such names as the Depository, pursuant to instructions from its direct or indirect participants or otherwise, shall instruct the Warrant Agent. The Warrant Agent shall deliver such Warrant Statements to the persons in whose names such Warrants are so registered.

(c) Transfer and Exchange of Book Entry Warrants . Book-Entry Warrants surrendered for exchange or for registration of transfer pursuant to clause (i) of the last sentence of this Section 6(c) or Section 6(h)(v) hereof shall be cancelled by the Warrant Agent. Such cancelled Book-Entry Warrants shall then be disposed of by or at the direction of the Company in accordance with applicable law. When Book-Entry Warrants are presented to or deposited with the Warrant Agent with a written request:

(i) to register the transfer of the Book-Entry Warrants; or

(ii) to exchange such Book-Entry Warrants for an equal number of Book-Entry Warrants of other authorized denominations,

the Warrant Agent shall register the transfer or make the exchange as requested if its requirements for such transactions are met; provided, however, that the Warrant Agent has received a written instruction of transfer in form satisfactory to the Warrant Agent, duly executed by the holder thereof or by his attorney, duly authorized in writing.

(d) Restrictions on Exchange or Transfer of a Book-Entry Warrant for a Beneficial Interest in a Global Warrant Certificate . A Book-Entry Warrant may not be exchanged for a beneficial interest in a Global Warrant Certificate except upon satisfaction of the requirements set forth in this Section 6(d) have been satisfied. Upon receipt by the Warrant Agent of appropriate instruments of transfer with respect to a Book-Entry Warrant, in form satisfactory to the Warrant Agent, together with written instructions directing the Warrant Agent to make, or to direct the Depository to make, an endorsement on the Global Warrant Certificate to reflect an increase in the number of Warrants represented by the Global Warrant Certificate equal to the number of Warrants represented by such Book-Entry Warrant (such instruments of transfer

4

and instructions to be duly executed by the holder hereof or the duly appointed legal representative thereof or by his attorney, duly authorized in writing, such signatures to be guaranteed by an eligible guarantor institution), then the Warrant Agent shall cancel such Book-Entry Warrant on the Warrant Register and cause, or direct the Depository to cause, in accordance with the standing instructions and procedures existing between the Depository and the Warrant Agent, the number of Warrants represented by the Global Warrant Certificate to be increased accordingly. If no Global Warrant Certificates are then outstanding, the Company shall issue, and the Warrant Agent shall countersign, a new Global Warrant Certificate representing the appropriate number of Warrants.

(e) Restrictions on Transfer and Exchange of Global Warrant Certificates . Notwithstanding any other provisions of this Warrant Agreement (other than the provisions set forth in Section 6(f)), unless and until it is exchanged in whole for a Book-Entry Warrant, a Global Warrant Certificate may not be transferred as a whole except by the Depository to a nominee of the Depository or by a nominee of the Depository to the Depository or another nominee of the Depository or by the Depository or any such nominee to a successor Depository or a nominee of such successor Depository.

(f) Book-Entry Warrants . If at any time:

(i) the Depository for the Global Warrant Certificates notifies the Company that the Depository is unwilling or unable to continue as Depository for the Global Warrant Certificates and a successor Depository for the Global Warrant Certificates is not appointed by the Company within 90 days after delivery of such notice; or

(ii) the Company, in its sole discretion, notifies the Warrant Agent in writing that it elects to exclusively cause the issuance of Book-Entry Warrants under this Warrant Agreement,

then the Warrant Agent, upon written instructions signed by an Appropriate Officer of the Company, shall register Book-Entry Warrants, in an aggregate number equal to the number of Warrants represented by the Global Warrant Certificates, in exchange for such Global Warrant Certificates, in such names and in such amounts as directed by the Depository or, in the absence of instructions from the Depository, the Company.

(g) Cancellation of Global Warrant Certificate . At such time as all beneficial interests in Global Warrant Certificates have either been exchanged for Book-Entry Warrants, redeemed, repurchased or cancelled, all Global Warrant Certificates shall be returned to, or cancelled and retained pursuant to applicable law by, the Warrant Agent.

(h) Obligations with Respect to Transfers and Exchanges of Warrants .

(i) To permit registrations of transfers and exchanges, the Company shall execute and the Warrant Agent is hereby authorized to countersign, in accordance with the provisions of Section 3 hereof and this Section 6 , Global Warrant Certificates, if applicable, or register Book-Entry Warrants, if applicable, as required pursuant to the provisions of this Section 6 and for the purpose of any distribution of additional Global Warrant Certificates contemplated by Section 12 hereof.

5

(ii) All Book-Entry Warrants and Global Warrant Certificates issued upon any registration of transfer or exchange of Book-Entry Warrants or Global Warrant Certificates shall be the valid obligations of the Company, entitled to the same benefits under this Warrant Agreement as the Book-Entry Warrants or Global Warrant Certificates surrendered upon such registration of transfer or exchange.

(iii) No service charge shall be made to a holder of Warrants for any registration, transfer or exchange but the Company may require payment of a sum sufficient to cover any stamp or other tax or other governmental charge that may be imposed on the holder in connection with any such exchange or registration of transfer.

(iv) So long as the Depository, or its nominee, is the registered owner of a Global Warrant Certificate, the Depository or such nominee, as the case may be, will be considered the sole owner or holder of the Warrants represented by such Global Warrant Certificate for all purposes under this Warrant Agreement. Except as provided in Section 6(b) hereof upon the exchange of a beneficial interest in a Global Warrant Certificate for a Book-Entry Warrants, owners of beneficial interests in a Global Warrant Certificate will not be entitled to have any Warrants registered in their names, and will not receive or be entitled to receive physical delivery of any such Warrants and will not be considered the owners or holders thereof under the Warrants or this Warrant Agreement. Neither the Company nor the Warrant Agent, in its capacity as registrar for such Warrants, will have any responsibility or liability for any aspect of the records relating to beneficial interests in a Global Warrant Certificate or for maintaining, supervising or reviewing any records relating to such beneficial interests.

(v) Subject to Sections 6(b) , (c) , (d)  hereof and this Section 6(h) , the Warrant Agent shall, upon receipt of all information required to be delivered hereunder, from time to time register the transfer of any outstanding Warrants in the Warrant Register, upon surrender of Global Warrant Certificates, if applicable, representing such Warrants at the Warrant Agent Office referred to in Section 20 hereof (the “Warrant Agent Office” ), duly endorsed, and accompanied by a completed form of assignment (or with respect to a Book-Entry Warrant, only such completed form of assignment), duly signed by the holder thereof or by the duly appointed legal representative thereof or by a duly authorized attorney, such signature to be guaranteed by an eligible guarantor institution. Upon any such registration of transfer, a new Global Warrant Certificate or a Warrant Statement, as the case may be, shall be issued to the transferee.

SECTION 7. Acknowledgment; Securities Law Compliance . Each Warrant holder, by its acceptance of any Warrant under this Warrant Agreement, acknowledges and agrees that the Warrants (including any Warrant Shares issued upon exercise thereof) were issued pursuant to an exemption from the registration requirement of Section 5 of the Securities Act provided by Section 1145 of the Bankruptcy Code or Section 4(2) of the Securities Act, and to the extent that a Warrant holder is an “ underwriter ” as defined in Section 1145(b)(1) of the Bankruptcy Code, such holder may not be able to sell or transfer any Warrants or Warrant Shares in the absence of an effective registration statement under the Securities Act or an exemption from registration thereunder.

6

SECTION 8. Terms of Warrants; Exercise of Warrants .

(a) Subject to the terms of this Warrant Agreement, each Warrant holder shall have the right, which may be exercised from the date of original issuance of the Warrant pursuant to the terms of this Warrant Agreement and prior to 5:00 p.m. New York City Time, on May 15, 2015 (the “Expiration Date” ), to exercise each Warrant and receive from the Company the number of fully paid and nonassessable Warrant Shares which the holder may at the time be entitled to receive on exercise of such Warrants and payment of the aggregate Exercise Price then in effect for such Warrant Shares. In addition, prior to the delivery of any shares of New Common Stock that the Company shall be obligated to deliver upon proper exercise of the Warrants, the Company shall comply with all applicable federal and state laws, rules and regulations which require action to be taken by the Company. Subject to the terms and conditions set forth herein, the Holder may exercise the Warrants by:

(i) providing written notice of such election (“ Warrant Exercise Notice ”) to exercise the Warrant to the Company and the Warrant Agent no later than 5:00 p.m. New York City time, on the Expiration Date, which Warrant Exercise Notice shall substantially be in the form of an election to purchase Warrant Shares set forth herein, properly completed and executed by the Holder;

(ii) delivering no later than 5:00 p.m. New York City time, on the business day immediately prior to the Settlement Date, this Warrant Certificate evidencing such Warrants to the Company; and

(iii) paying the applicable Exercise Amount, together with any applicable taxes and governmental charges.

(b) The Holder shall have the right, in lieu of paying the Exercise Amount in cash, to instruct the Company to reduce the number of shares of New Common Stock issued purchased pursuant to the exercise of the Warrants in accordance with the following formula:

7

The term “ Market Price ” means, as of any date of determination but calculated as the average over the preceding 20 days on which the New Common Stock has traded, (i) the closing price per share of New Common Stock on such date published in The Wall Street Journal or, if no such closing price on such date is published in The Wall Street Journal, the average of the closing bid and asked prices on such date, as officially reported on the principal securities exchange on which the New Common Stock is then listed or admitted to trading; or (ii) if the New Common Stock is not then listed or admitted to trading on any securities exchange but is designated as a national market system security by the National Association of Securities Dealers, Inc., the last trading price of the New Common Stock on such date; or (iii) if there shall have been no trading on such date or if the New Common Stock are not so designated, the average of the reported closing bid and asked prices of the New Common Stock on such date as shown by the National Market System of the National Association of Securities Dealers, Inc. Automated Quotations System and reported by any member firm of the New York Stock Exchange selected by the Company; or (iv) if none of (i), (ii) or (iii) is applicable, the “Market Price” shall be the fair value thereof, determined in good faith by the Company.

To the extent a Warrant Exercise Notice is delivered in respect of Warrant prior to 5:00 p.m., New York City time, on the Expiration Date, but the deliveries and payments specified in clause (ii) and (iii) above are effected thereafter but no later than 5:00 p.m., New York City time, on the Settlement Date, the Warrants shall be nonetheless deemed exercised prior to the Expiration Date for the purposes of this Warrant Agreement.

(c) Subject to the adjustments set forth in Section 12 hereof, each Warrant, when exercised, will entitle the holder thereof to purchase one share of New Common Stock at the Exercise Price then in effect for such share of New Common Stock. Each Warrant not exercised pursuant to this Warrant Agreement prior to the Expiration Date shall become void and all rights thereunder and all rights in respect thereof under this Warrant Agreement shall cease as of the Expiration Date.

(d) The Exercise Amount shall be payable in lawful money of the United States of America either by certified or official bank check made payable to the order of the Company (or if agreed to in the sole and absolute discretion of the Company, by wire transfer in immediately available funds to an account arranged with the Company prior to exercise).

(e) Any exercise of a Warrant pursuant to the terms of this Warrant Agreement shall be irrevocable and shall constitute a binding agreement between the holder and the Company, enforceable in accordance with its terms.

(f) The Warrant Agent shall:

(i) examine all Warrant Exercise Notices and all other documents delivered to it by or on behalf of holders to ascertain whether, on their face, such Warrant Exercise Notices and any such other documents have been executed and completed in accordance with their terms;

(ii) where a Warrant Exercise Notice or other document appears on its face to have been improperly completed or executed or some other irregularity in connection with the exercise of the Warrant exists, the Warrant Agent shall endeavor to inform the appropriate parties (including the person submitting such instrument) of the need for fulfillment of all requirements, specifying those requirements which appear to be unfulfilled;

8

(iii) inform the Company of and cooperate with and assist the Company in resolving any reconciliation problems between the Warrant Exercise Notices received and delivery of Warrants to the Warrant Agent’s account;

(iv) advise the Company, no later than three business days after receipt of a Warrant Exercise Notice, of (x) the receipt of such Warrant Exercise Notice and the number of Warrants exercised in accordance with the terms and conditions of this Warrant Agreement, (y) the instructions with respect to delivery of the shares of New Common Stock of the Company deliverable upon such exercise, subject to the timely receipt from the Depository of the necessary information, and (z) such other information as the Company shall reasonably require; and

(v) subject to the New Common Stock being made available to the Warrant Agent by or on behalf of the Company for delivery to the Depository, liaise with the Depository and endeavor to effect such delivery to the relevant accounts at the Depository in accordance with its requirements.

(g) All questions as to the validity, form and sufficiency (including time of receipt) of a Warrant exercise shall be determined by the Company in its sole discretion, which determination shall be final and binding. The Warrant Agent shall incur no liability for or in respect of and, except to the extent such liability arises from the Warrant Agent’s gross negligence, willful misconduct or bad faith, shall be indemnified and held harmless by the Company for acting or refraining from acting upon, or as a result of such determination by the Company. The Company reserves the right to reject any and all Warrant Exercise Notices not in proper form or for which any corresponding agreement by the Company to exchange would, in the opinion of the Company, be unlawful. Such determination by the Company shall be final and binding on the holders, absent manifest error. Moreover, the Company reserves the absolute right to waive any of the conditions to the exercise of Warrants or defects in Warrant Exercise Notices with regard to any particular exercise of Warrants. The Company shall be und