AMENDMENT NO. 3

EXHIBIT 4.1

AMENDMENT NO. 3

This AMENDMENT No. 3 dated as of October 10, 2003 (this “Amendment”), is among COINSTAR, INC., a Delaware corporation (the “Borrower”), each of the lenders that is a party to the Agreement (as defined herein below), and BANK OF AMERICA, N.A., as Administrative Agent (the “Administrative Agent”).

INTRODUCTION

Reference is made to the Credit Agreement dated as of April 18, 2002, as amended by Amendment No. 1 dated January 1, 2003 and Amendment No. 2 dated June 3, 2003 (collectively, the “Agreement”), among the Borrower, the Lenders (as defined therein), and the Administrative Agent. The Borrower, each of the undersigned lenders, and the Administrative Agent have agreed to modify certain financial covenants and make other amendments to the Agreement as set forth herein in connection with the Borrower’s proposed business activities.

THEREFORE, in connection with the foregoing and for other good and valuable consideration, the parties hereto hereby agree as follows:

1. Defined Terms. Unless otherwise defined in this Amendment, terms used in this Amendment which are defined in the Agreement shall have the meanings assigned to such terms in the Agreement.

2. Amendment.

(a) Section 6.14 is deleted in its entirety and replaced with the following:

6.14 Intentionally Omitted.

(b) Section 7.06(d) is deleted in its entirety and replaced with the following:

(d) From October 10, 2003 through the remainder of the term of this Agreement:

(i) Borrower may spend up to $25,000,000 to purchase, redeem or otherwise acquire shares of its capital stock or warrants, rights or options to acquire any such shares for cash (collectively, “Capital Stock Acquisitions”); provided no Default existed before or would exist immediately after giving effect to such proposed action; and

(ii) Borrower may spend an amount in excess of $25,000,000 to make Capital Stock Acquisitions; provided no Default existed before or would exist immediately after giving effect to such proposed action; and further provided that if Borrower elects to make Capital Stock Acquisitions pursuant to this subsection

(ii), it shall be an Event of Default if at any time following such action the Total Outstandings exceed $40,000,000.

(c) Section 7.09 is deleted in its entirety and replaced with the following:

7.09 Capital Expenditures. Make or become legally obligated to make any expenditure in respect of the purchase or other acquisition of any fixed or capital asset (excluding normal replacements and maintenance which are properly charged to current operations), except that:

(a) if Total Outstandings of Borrower and its Subsidiaries at any time during a fiscal year exceed $40,000,000, Borrower and its Subsidiaries may make capital expenditures in the ordinary course of business not exceeding, in the aggregate during each fiscal year set forth below, the amount set forth opposite such fiscal year:

or

(b) if Total Outstandings of Borrower and its Subsidiaries do not at any time during a fiscal year exceed $40,000,000, Borrower and its Subsidiaries may make an unlimited amount of capital expenditures in the ordinary course of business during such fiscal year.

(d) Section 7.12(d) is deleted in its entirety and replaced with the following:

(d) Consolidated EBITDA. Beginning with the fiscal quarter of Borrower and its Subsidiaries ending December 31, 2003 and for each such fiscal quarter thereafter through the remainder of the term of this Agreement, permit the Consolidated EBITDA for any such quarter ending on the month and day set forth in the table below to be less than the minimum Consolidated EBITDA set forth opposite such month and day:

(e) Article I and Article V of Schedule 2 to Exhibit C to the Agreement is hereby deleted in its entirety and replaced with the Article I and Article V set forth in Exhibit A attached

2

hereto and made a part hereof. Article VII of Exhibit A attached hereto is hereby added to the end of Schedule 2 to Exhibit C to the Agreement as Article VII thereof.

3. Representations and Warranties. The Borrower represents and warrants that (a) the execution, delivery, and performance of this Amendment are within the corporate power and authority of the Borrower and have been duly authorized by appropriate proceedings, (b) this Amendment constitutes legal, valid, and binding obligations of the Borrower enforceable in accordance with its terms, except as limited by applicable bankruptcy, insolvency, reorganization, moratorium, or similar laws affecting the rights of creditors generally and general principles of equity, and (c) upon the effectiveness of this Amendment, no Event of Default shall exist under the Agreement and there shall have occurred no event which with notice or lapse of time would become an Event of Default under the Agreement, as amended.

4. Effect on Loan Documents. Except as amended herein, the Loan Documents remain in full force and effect as originally executed. Nothing herein shall act as a waiver of the Administrative Agent’s or the Lenders’ rights under the Loan Documents as amended, including the waiver of any default or event of default, however denominated, except as specifically provided herein. The Borrower must continue to comply with the terms of the Loan Documents, as amended. This Amendment is a Loan Document for the purposes of the provisions of the other Loan Documents. Without limiting the foregoing, any breach of representations, warranties, and covenants under this Agreement shall be a default under the other Loan Documents.

5. Effectiveness. This Amendment shall become effective and the Agreement shall be amended as provided in this Amendment effective on the date first set forth above upon the occurrence of the following conditions precedent:

(a) the Administrative Agent shall have received duly executed counterparts hereof signed by the Borrower, the Administrative Agent, and the Required Lenders; and,

(b) the Borrower shall have paid all fees and expenses required in connection herewith.

6. Miscellaneous. The miscellaneous provisions of the Agreement apply to this Amendment. This Amendment may be signed in any number of counterparts, each of which shall be an original and may be delivered by facsimile.

THIS WRITTEN AMENDMENT AND THE LOAN DOCUMENTS REPRESENT THE FINAL AGREEMENT BETWEEN THE PARTIES AND MAY NOT BE CONTRADICTED BY EVIDENCE OF PRIOR, CONTEMPORANEOUS, OR SUBSEQUENT ORAL AGREEMENTS OF THE PARTIES.

THERE ARE NO UNWRITTEN ORAL AGREEMENTS BETWEEN THE PARTIES.

3

EXECUTED as of the date first above written.

4

5

6

7

8

9

10

EXHIBIT A