COINSTAR, INC. LETTER AGREEMENT REGARDING RETENTION INCENTIVES, RELEASE AND NONCOMPETITION

Exhibit 10.3

COINSTAR, INC.

LETTER AGREEMENT REGARDING RETENTION INCENTIVES,

RELEASE AND NONCOMPETITION

April 10, 2009

Timothy Hale

One Tower Lane, Suite 1200

Oakbrook Terrace, IL 60181

This Letter Agreement (“Agreement”) confirms the agreement between Coinstar, Inc., a Delaware corporation, (the “Company”), and the above-named person (“you” or “Employee”) with respect to certain employment-related agreements. For purposes of this Agreement, “Company Party” means the Company and any of the Company’s subsidiaries, including but not limited to Redbox Automated Retail, LLC, a Delaware limited liability company (“Redbox”).

1. Employment at Will. You will be employed at-will following the execution of this Agreement, meaning that either you or the relevant Company Party that employs you may terminate the employment relationship at any time for any reason, with or without cause.

2. Incentives. The Compensation Committee of Coinstar’s Board of Directors has granted you the following employment incentives subject to the terms and conditions set forth in Exhibit A:

(a) Stock Option. An option to acquire shares of Coinstar common stock in an amount and for the exercise price set forth in the “Stock Option” section in Exhibit A, such option to vest as specified in such “Stock Option” section.

(b) Cash. Cash payments to be made in the amounts and at the times set forth in the “Cash” section in Exhibit A.

3. Confidentiality. In connection with the execution and delivery of this Agreement, you will execute and deliver to the Company the Company’s standard form Proprietary Information and Invention Agreement (“PIIA”), which PIIA shall survive the termination of this Agreement.

4. No Conflicting Agreements. You represent that your performance of all the terms of this Agreement and the PIIA does not and will not breach any agreement to keep in confidence proprietary information, knowledge or data acquired by you in confidence or in trust prior to this Agreement, and you will not disclose to any Company Party, or induce any Company Party to use, any confidential or proprietary information or material belonging to any previous employer or others. You agree not to enter into any agreement either written or oral in conflict with the provisions of this Agreement.

5. Release.

(a) In consideration for the grant of incentives as specified above and other benefits provided in this Agreement, you release, waive and discharge each Company Party and their respective directors, officers, employees and agents from any and all claims, liabilities or obligations that you may have, whether direct or indirect, known or unknown, contingent or accrued, arising in connection with any agreements, activities or arrangements with or relating to any Company Party. This release includes, but is not limited to, any claims for wages, bonuses, employment benefits, stock options, equity awards, or damages of any kind, arising out of any common law torts, arising out of any contracts, any theory of retaliation, any theory of discrimination or harassment, or any federal or state law, including, without limitation, Title VII of the Civil Rights Act of 1964 as amended, the Civil Rights Act of 1991, the Civil Rights Act of 1866, 42 U.S.C. § 1981, the Americans with Disabilities Act, the Age Discrimination in Employment Act, the Older Workers Benefit Protection Act, the Family and Medical Leave Act, the Employee Retirement Income Security Act, the Washington Law Against Discrimination, or any other legal limitation on or regulation of the employment relationship. This waiver and release does not preclude you from filing a lawsuit to enforce your rights under this Agreement and it does not release, waive or discharge claims arising after the date of this Agreement.

(b) You acknowledge that you have carefully read and fully understand all aspects of this Agreement including the fact that this Agreement releases any claims that you might have against any Company Party. You agree and acknowledge that you have not relied upon any representations or statements not set forth in this Agreement or made by any Company Party or their agents and representatives. You acknowledge that you have been advised to consult with an attorney prior to executing the Agreement, and that you have either done so or you knowingly waive the right to do so, and you now enter into this Agreement without duress or coercion from any source. You agree that you have been provided the opportunity to consider for twenty-one (21) days whether to enter into this Agreement, and you have voluntarily chosen to enter into it on this date. You may revoke this Agreement for a period of seven (7) days following the execution of this Agreement; this Agreement shall become effective following expiration of this seven (7) day period.

6. Noncompetition; Nondisclosure; Nondisparagement.

(a) You acknowledge that the nature of your employment with one or more Company Parties has given you access to trade secrets and confidential information, including information about the Company’s technology and customers. Therefore, during the one (1) year following termination of employment for whatever reason, you will not engage in, be employed by, perform, services for, participate in the ownership, management, control or operation of, or otherwise be connected with, either directly or indirectly, any business or activity whose efforts are in competition with (i) the products or services manufactured or marketed by the Company at the time of this Agreement, or (ii) the products or services which have been under research or development by the Company during the term of your employment, and which the Company has demonstrably considered for further development or commercialization. The geographic scope of this restriction shall extend to anywhere the Company is doing business, has done business or intends to do business. You acknowledge that the restrictions are reasonable and necessary for protection of the business and goodwill of the Company.

(b) You further agree that you will not at any time disclose confidential information about the Company relating to its business, technology, practices, products, marketing, sales, services, finances or legal affairs.

(c) Following your termination for any reason, you and the Company shall refrain from making any derogatory comment in the future to the press or any individual or entity regarding the other that relates to their activities or relationship prior to the date of termination, which comment would likely cause material damage or harm to the business interests or reputation of you or the Company. You acknowledge

2

that the non-disparagement provisions of this Section 6(c) are essential to the Company, that the Company would not enter, into this Agreement if it did not include this Section 6(c), and that damages sustained by the Company as a result of a breach of this Section 6(c) cannot be adequately quantified or remedied by damages alone. Accordingly, the Company shall be entitled to injunctive and other equitable relief to prevent or curtail any breach of this Section 6(c).

7. Amendment. No amendment, modification, waiver, termination or discharge of the terms of this Agreement will be valid unless set forth in a writing signed by you and the Company.

8. Assignment. This Agreement is personal to you and shall not be assignable by you. The Company or the relevant Company Party may assign its rights hereunder to (a) any corporation resulting from any merger, consolidation or other reorganization to which the Company or the relevant Company Party is a party, or (b) any corporation, partnership, association or other person to which the Company or the relevant Company Party may transfer all or substantially all of the assets and business of the Company or the relevant Company Party existing at such time. All of the terms and provisions of this Agreement shall be binding upon and shall inure to the benefit of and be enforceable by the parties hereto and their respective successors and permitted assigns.

9. Severability. If any provision of this Agreement shall be held invalid, illegal or unenforceable in any jurisdiction, for any reason, including, without limitation, the duration of such provision, its geographical scope or the extent of the activities prohibited or required by it, then, to the full extent permitted by law (a) all other provisions hereof shall remain in full force and effect in such jurisdiction and shall be liberally construed in order to carry out the intent of the parties hereto as nearly as may be possible, (b) such invalidity, illegality or unenforceability shall not effect the validity, legality or enforceability of any other provision hereof, and (c) any court having jurisdiction thereover shall have the power to reform such provision to the extent necessary for such provision to be enforceable under applicable law.

10. Notices. All notices, requests and other communications called for by this Agreement will be deemed to have been given if made in writing and delivered via (i) nationally recognized overnight courier, or (ii) personal delivery, if to you at the address set forth above and if to the Company at 1800 114th Avenue SE, Bellevue, WA 98004, Attn.: General Counsel, or other addresses as either party specifies to the other.

11. Tax Withholding. The Company shall be entitled to withhold from any amounts paid hereunder such amounts as the Company determines are or may be required by law.

12. Governing Law. The validity, performance and construction of this Agreement will be governed by the laws of the State of Washington without regard to principles of conflicts of laws.

[The remainder of this page is intentionally left blank.]

3

SIGNATURE PAGE TO LETTER AGREEMENT REGARDING RETENTION INCENTIVES,

RELEASE AND NONCOMPETITION

EXHIBIT A

TO LETTER AGREEMENT REGARDING RETENTION INCENTIVES,

RELEASE AND NONCOMPETITION

Timothy Hale

Stock Option

Subject to the applicable terms and conditions regarding such option, including but not limited to the terms and conditions set forth at http://www.fidelity.com with respect thereto, you have been granted an option to purchase 11,793 shares of Common Stock of the Company (the “Stock Option’”). The Stock Option is subject to the terms and conditions set forth in the Stock Option Grant Notice, the Stock Option Agreement and the 1997 Amended and Restated Equity Incentive Plan governing such option, including but not limited to the vesting schedule applicable thereto.

Cash

Subject to your continued employment or service relationship with the Company through

(a) February 26, 2010, at that time you will be paid a cash payment of $213,658.25,

(b) February 26, 2011, at that time you will be paid a cash payment of $82,836.40, and

(c) February 26, 2012, at that time you will be paid a cash payment of $39,272.72.