EMPLOYMENT AGREEMENT COINSTAR, INC.

Exhibit 10.1

EMPLOYMENT AGREEMENT

COINSTAR, INC.

and

J. SCOTT DI VALERIO

Executed and effective on January 19, 2010

EMPLOYMENT AGREEMENT

This Employment Agreement (this “Agreement”), executed and effective on January 19, 2010 between Coinstar, Inc., a Delaware corporation (“Employer”), and J. Scott Di Valerio (“Employee”);

W I T N E S S E T H:

WHEREAS, Employer and Employee wish to document certain understandings and agreements; and

WHEREAS, Employer desires to employ Employee upon the terms and conditions set forth herein; and

WHEREAS, Employee is willing to provide services to Employer upon the terms and conditions set forth herein;

A G R E E M E N T S:

NOW, THEREFORE, for and in consideration of the foregoing premises and for other good and valuable consideration, the sufficiency and receipt of which are hereby acknowledged, Employer and Employee hereby agree as follows:

1. CHIEF FINANCIAL OFFICER

1.1 Employment

Employer will employ Employee and Employee will provide services to Employer during the Term (as defined below). During the period January 19, 2010 through March 1, 2010 Employee will work with the Company on transition issues and report directly to the Company’s Chief Executive Officer. Effective March 2, 2010, Employee will assume the title, authority and responsibilities of Chief Financial Officer.

1.2 Attention and Effort

Employee will devote all of his professional productive time, ability, attention and effort to Employer’s business and will skillfully serve its interests during the Term.

1.3 Term

Employee’s term of employment under this Agreement shall begin as of the effective date of this Agreement and shall continue until terminated pursuant to Section 2 of this Agreement (the “Term”).

1.4 Compensation

During the Term, Employer agrees to pay or cause to be paid to Employee, and Employee agrees to accept in exchange for the services rendered hereunder by him, the following compensation:

(a) Base Salary

Employee’s compensation shall consist, in part, of an annual base salary of four hundred fifty thousand dollars ($450,000) before all customary payroll deductions. Such annual base salary shall be paid in substantially equal installments and at the same intervals as other officers of Employer are paid. Employee’s salary shall be reviewed by Employer’s Compensation Committee as appropriate to determine in its discretion whether it is appropriate to increase the base salary.

(b) Bonus

Employee shall be eligible for cash bonuses consistent with the existing program for executive officers, provided performance targets applicable to such bonuses are met.

1.5 Benefits

During the Term, Employee will be entitled to participate, subject to and in accordance with applicable eligibility requirements, in fringe benefit programs as shall be provided from time to time by, to the extent required, action of Employer’s Board of Directors.

2. TERMINATION

Employment of Employee pursuant to this Agreement may be terminated as follows, but in any case, the provisions of Section 4 hereof shall survive the termination of this Agreement and the termination of Employee’s employment hereunder:

2.1 By Employer

With or without Cause (as defined below), Employer may terminate the employment of Employee at any time during the Term upon giving Notice of Termination (as defined below).

2.2 By Employee

Employee may terminate his employment at any time, for any reason, upon giving Notice of Termination.

-2-

2.3 Automatic Termination

This Agreement and Employee’s employment hereunder shall terminate automatically upon the death or total disability of Employee. The term “total disability” as used herein shall mean Employee’s inability to perform the duties set forth in Section 1 hereof for a period or periods aggregating 180 calendar days in any 12-month period as a result of physical or mental illness, loss of legal capacity or any other cause beyond Employee’s control, unless Employee is granted a leave of absence by the Employer. Employee and Employer hereby acknowledge that Employee’s ability to perform the duties specified in Section 1 hereof is of the essence of this Agreement. Termination hereunder shall be deemed to be effective (a) at the end of the calendar month in which Employee’s death occurs or (b) immediately upon a determination by the Employer of Employee’s total disability, as defined herein.

2.4 Termination in Connection With a Change in Control

Concurrent with the commencement of Employee’s employment hereunder, Employee and the Company shall enter into a Change of Control Agreement, in the form attached hereto as Exhibit A. Notwithstanding Sections 3.1 and 3.2 of this Agreement and in full substitution therefor, if Employee’s employment terminates under circumstances described in the Change of Control Agreement, Employee’s rights upon termination will be governed by the terms of the Change of Control Agreement and his right to termination payments under this Employment Agreement shall cease.

2.5 Notice

The term “Notice of Termination” shall mean at least 30 days’ written notice of termination of Employee’s employment, during which period Employee’s employment and performance of services will continue; provided, however, that Employer may, upon notice to Employee and without reducing Employee’s compensation during such period, excuse Employee from any or all of his duties during such period. The effective date of the termination of Employee’s employment hereunder shall be the date on which such 30-day period expires.

3. TERMINATION PAYMENTS

In the event of termination of the employment of Employee during the Term, all compensation and benefits set forth in this Agreement shall terminate except as specifically provided in this Section 3:

3.1 Termination by Employer Without Cause or by Employee for Good Reason

If, during the Term, Employer terminates Employee’s employment without Cause or Employee terminates his employment for Good Reason, Employee shall be entitled to receive (a) termination payments equal to twelve (12) months’ annual base salary, (b) any unpaid annual base salary which has accrued for services already performed as of the date

-3-

termination of Employee’s employment becomes effective and (c) the product of (x) the annual bonus payable with respect to the fiscal year in which the date of termination occurs and (y) a fraction, the numerator of which is the number of days Employee was employed by Employer during the fiscal year in which the date of termination occurs, and the denominator of which is 365. All amounts payable pursuant to this Section 3.1 (or pursuant to Section 3.2) shall be reduced for applicable deductions and tax withholding. If, as a result of the termination of Employee’s employment without Cause or for Good Reason, Employee and Employee’s spouse and dependent children are eligible for and timely (and properly) elect to continue coverage under Employer’s group health plan(s) in accordance with Code Section 4980B(f) (“COBRA”), Employer shall pay the premium for such coverage for a period of twelve (12) months following the date of Employee’s termination or until Employee is no longer entitled to COBRA continuation coverage under Employer’s group health plan(s), whichever period is the shorter. All other Employer benefits cease on the date of termination by Employer without Cause or by Employee for Good Reason. If, during the Term, Employee is terminated by Employer for Cause or Employee terminates his employment other than for Good Reason, Employee shall not be entitled to receive any of the foregoing benefits, other than those set forth in Section 3.1(b) above.

3.2 Termination by Employer for Cause or by Employee Other Than for Good Reason

In the case of the termination of Employee’s employment by Employer for Cause or by Employee other than for Good Reason, Employee shall not be entitled to any payments hereunder, other than those set forth in Section 3.1(b) hereof if such termination occurs during the Term.

3.3 Payment Schedule

All amounts payable pursuant to Section 3.1(b), 3.1(c) and 3.2 hereof shall be paid to Employee at the same time such amounts would have been paid to Employee had Employee’s employment not been terminated (or at such earlier time as is required by law). All amounts payable pursuant to Section 3.1(a) hereof shall be paid to Employee in twelve (12) equal monthly installments, beginning with the month following the month containing the date of Employee’s termination and continuing for eleven (11) consecutive months thereafter. For purposes of Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”), each such installment shall be treated as a separate payment.

3.4 Cause

Wherever reference is made in this Agreement to termination being with or without Cause, “Cause” is limited to the occurrence of one or more of the following events:

(a) Failure or refusal to carry out the lawful duties of Employee described in Section 1 hereof or any directions of the Board of Directors of Employer, which directions are reasonably consistent with the duties herein set forth to be performed by Employee;

-4-

(b) Violation by Employee of a state or federal criminal law involving the commission of a crime against Employer or a felony;

(c) Current use by Employee of illegal substances; deception, fraud, misrepresentation or dishonesty by Employee; any act or omission by Employee which substantially impairs Employer’s business, good will or reputation; or

(d) Any other material violation of any provision of this Agreement.

3.5 Good Reason

(a) For purposes of this Agreement, subject to Section 3.5(b), “Good Reason” means the occurrence or existence of any of the following events or conditions without Employee’s express written consent:

(i) A material diminution in Employee’s annual base salary;

(ii) A material diminution in Employee’s authority, duties or responsibilities as contemplated by Section 1.1 hereof, excluding for this purpose reasonable changes in particular duties and reporting responsibilities which may result from Employer becoming part of a larger business organization at some future time provided that such changes in the aggregate do not result in a material alteration in Employee’s authority, duties or responsibilities;

(iii) A relocation of Employee’s principal place of employment to a location more than 50 miles from the Seattle metropolitan area, except for required travel on Employer’s business to an extent substantially consistent with Employee’s duties and responsibilities; or

(iv) Any other action or inaction by Employer that constitutes a material breach by Employer of this Agreement.

(b) Notwithstanding any provision in this Agreement to the contrary, termination of employment by Employee will not be for Good Reason unless (i) Employee notifies Employer in writing of the occurrence or existence of the event or condition which Employee believes constitutes Good Reason within 90 days of the occurrence or initial existence of such event or condition (which notice specifically identifies such event or condition), (ii) Employer fails to remedy such event or condition within 30 days after the date on which it receives such notice (the “Remedial Period”), and (iii) Employee actually terminates employment within 90 days after the expiration of the Remedial Period and before Employer remedies such event or condition. If Employee terminates employment before the expiration of the Remedial Period or after Employer remedies the event or condition (even if after the end of the Remedial Period), then Employee’s termination will not be considered to be for Good Reason.

-5-

3.6 Code Section 409A

The Employer makes no representations or warranties to Employee with respect to any tax, economic or legal consequences of this Agreement or any payments or other benefits provided hereunder, including without limitation under Code Section 409A, and no provision of this Agreement shall be interpreted or construed to transfer any liability for failure to comply with Code Section 409A or any other legal requirement from Employee or any other person to the Employer, any of its affiliates or any other person. Employee, by executing this Agreement, shall be deemed to have waived any claim against the Employer, its affiliates and any other person with respect to any such tax, economic or legal consequences. However, the parties intend that this Agreement and the payments and other benefits provided hereunder shall be exempt from the requirements of Code Section 409A to the maximum extent possible, whether pursuant to the short-term deferral exception described in Treasury Regulation Section 1.409A-1(b)(4), the involuntary separation pay plan exception described in Treasury Regulation Section 1.409A-1(b)(9)(iii), or otherwise. To the extent Code Section 409A is applicable to this Agreement (and such payments and benefits), the parties intend that this Agreement (and such payments and benefits) shall comply with the deferral, payout and other limitations and restrictions imposed under Code Section 409A. Notwithstanding any other provision of this Agreement to the contrary, this Agreement shall be interpreted, operated and administered in a manner consistent with such intentions. Without limiting the generality of the foregoing, and notwithstanding any other provision of this Agreement to the contrary, with respect to any payments and benefits under this Agreement to which Code Section 409A applies, all references in this Agreement to termination of Employee’s employment are intended to mean Employee’s “separation from service,” within the meaning of Code Section 409A(a)(2)(A)(i). In addition, if Employee is a “specified employee,” within the meaning of Code Section 409A(a)(2)(B)(i), when he/she separates from service, within the meaning of Code Section 409A(a)(2)(A)(i), then to the extent necessary to avoid subjecting Employee to the imposition of any additional tax under Code Section 409A, amounts that would otherwise be payable under this Agreement during the six-month period immediately following Employee’s separation from service shall not be paid to Employee during such period, but shall instead be accumulated and paid to Employee (or, in the event of Employee’s death, Employee’s estate) in a lump sum on the first business day following the earlier of (a) the date that is six months after Employee’s separation from service or (b) Employee’s death.

4. NONCOMPETITION, NONDISCLOSURE AND NONDISPARAGEMENT

(a) The nature of Employee’s employment with Employer has given Employee access to trade secrets and confidential information, including information about its technology and customers. Therefore, during the one (1) year following termination of employment for whatever reason, Employee 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 Employer at the time of this Agreement, or (ii) the products or services which have been under research or

-6-

development by Employer during the Term, and which Employer has demonstrably considered for further development or commercialization. The geographic scope of this restriction shall extend to anywhere Employer is doing business, has done business or intends to do business. Employee acknowledges that the restrictions are reasonable and necessary for protection of the business and goodwill of Employer.

If, within one year of the date of termination, Employee violates this Section 4, Employee shall forfeit any remaining termination payments provided under Section 3.

(b) Employee further agrees that he will not at any time disclose confidential information about Employer relating to its business, technology, practices, products, marketing, sales, services, finances or legal affairs.

(c) Following termination of Employee for any reason, Employee and Employer 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 Employee or Employer. Employee acknowledges that the non-disparagement provisions of this Section 4(c) are essential to Employer, that Employer would not enter into this Agreement if it did not include this Section 4(c), and that damages sustained by Employer as a result of a breach of this Section 4(c) cannot be adequately quantified or remedied by damages alone. Accordingly, Employer shall be entitled to injunctive and other equitable relief to prevent or curtail any breach of this Section 4(c).

5. REPRESENTATIONS AND WARRANTIES OF EMPLOYEE

Employee represents and warrants that neither the execution nor the performance of this Agreement nor the Proprietary Information and Invention Agreement by Employee will violate or conflict in any way with any other agreement by which Employee may be bound, or with any other duties imposed upon Employee by corporate or other statutory or common law.

6. FORM OF NOTICE

All notices given hereunder shall be given in writing, shall specifically refer to this Agreement and shall be personally delivered or sent by registered or certified mail, return receipt requested, at the address set forth below or at such other address as may hereafter be designated by notice given in compliance with the terms hereof:

-7-

If notice is mailed, such notice shall be effective upon mailing, or if notice is personally delivered, it shall be effective upon receipt.

7. ASSIGNMENT

This Agreement is personal to Employee and shall not be assignable by Employee. Employer may assign its rights hereunder to (a) any corporation or other entity resulting from any merger, consolidation or other reorganization to which Employer is a party or (b) any corporation, partnership, association or other person to which Employer may transfer all or substantially all of the assets and business of Employer 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.

8. WAIVERS

No delay or failure by any party hereto in exercising, protecting or enforcing any of its rights, titles, interests or remedies hereunder, and no course of dealing or performance with respect thereto, shall constitute a waiver thereof. The express waiver by a party hereto of any right, title, interest or remedy in a particular instance or circumstance shall not constitute a waiver thereof in any other instance or circumstance. All rights and remedies shall be cumulative and not exclusive of any other rights or remedies.

9. ARBITRATION

Any controversies or claims arising out of or relating to this Agreement shall be fully and finally settled by arbitration in accordance with the Commercial Arbitration Rules of the American Arbitration Association then in effect (the “AAA Rules”), conducted by one arbitrator either mutually agreed upon by Employer and Employee or chosen in accordance with the AAA Rules, except that the parties thereto shall have any right to discovery as would be permitted by the Federal Rules of Civil Procedure for a period of 90 days following the commencement of such arbitration and the arbitrator thereof shall resolve any dispute which arises in connection with such discovery. The prevailing party shall be entitled to costs, expenses and reasonable attorneys’ fees, and judgment upon the award rendered by the arbitrator may be entered in any court having jurisdiction thereof. This provision shall not preclude Employer from seeking court enforcement or relief based upon an alleged violation of Employee’s obligations under any noncompetition or non-disclosure agreement.

-8-

10. AVAILABILITY AND CONSULTATION

If Employee’s employment with Employer terminates for any reason, Employee will thereafter make himself reasonably available to Employer and counsel for Employer for the purpose of enabling Employer to defend against any legal claims in which Employer determines he may have knowledge or information. Employer will reimburse Employee for reasonable out-of-pocket expenses incurred in connection with any consultations under this Section 10.

11. AMENDMENTS IN WRITING

No amendment, modification, waiver, termination or discharge of any provision of this Agreement, nor consent to any departure therefrom by either party hereto, shall in any event be effective unless the same shall be in writing, specifically identifying this Agreement and the provision intended to be amended, modified, waived, terminated or discharged and signed by Employer and Employee, and each such amendment, modification, waiver, termination or discharge shall be effective only in the specific instance and for the specific purpose for which given. No provision of this Agreement shall be varied, contradicted or explained by any oral agreement, course of dealing or performance or any other matter not set forth in an agreement in writing and signed by Employer and Employee.

12. APPLICABLE LAW

This Agreement shall in all respects, including all matters of construction, validity and performance, be governed by, and construed and enforced in accordance with, the laws of the state of Washington, without regard to any rules governing conflicts of laws.

13. 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 affect the validity, legality or enforceability of any other provision hereof, and (c) any court or arbitrator having jurisdiction thereover shall have the power to reform such provision to the extent necessary for such provision to be enforceable under applicable law.

14. HEADINGS

All headings used herein are for convenience only and shall not in any way affect the construction of, or be taken into consideration in interpreting, this Agreement.

-9-

15. COUNTERPARTS

This Agreement, and any amendment or modification entered into pursuant to Section 11 hereof, may be executed in any number of counterparts, each of which counterparts, when so executed and delivered, shall be deemed to be an original and all of which counterparts, taken together, shall constitute one and the same instrument.

16. ENTIRE AGREEMENT

Except for (a) the Proprietary Information and Invention Agreement executed by Employee on January 19, 2010, and (b) the Change of Control Agreement executed by the Employee on January 19, 2010, this Agreement sets forth the entire understanding between Employee and Employer, superseding any prior agreements or understandings, express or implied, pertaining to the terms of Employee’s employment with Employer. Employee acknowledges that in executing this Agreement, he does not rely upon any representation or statement by any representative or agent of Employer concerning the subject matter of this Agreement.

IN WITNESS WHEREOF, the parties have executed and entered into this Agreement on the date set forth above.

-10-

EXHIBIT A

CHANGE OF CONTROL AGREEMENT