CHANGE OF CONTROL AGREEMENT

Exhibit 10.2

CHANGE OF CONTROL AGREEMENT

This Change of Control Agreement (this “Agreement”), dated as of August 5, 2005, is between Coinstar, Inc. (the “Employer”), and Brian V. Turner (the “Employee”). This Agreement is an exhibit to that certain Employment Agreement dated as of August 5, 2005 between the Employer and the Employee (the “Employment Agreement”).

The Board of Directors of the Employer (the “Board”) has determined that it is in the best interests of the Employer and its stockholders to ensure that the Employer will have the continued dedication of the Employee, notwithstanding the possibility, threat or occurrence of a Change of Control (as defined in Appendix A to this Agreement, which is incorporated herein by this reference) of the Employer. The Board believes it is imperative to diminish the inevitable distraction of the Employee arising from the personal uncertainties and risks created by a pending or threatened Change of Control, to encourage the Employee’s full attention and dedication to the Employer currently and in the event of any threatened or pending Change of Control, to encourage the Employee’s willingness to serve a successor in an equivalent capacity, and to provide the Employee with reasonable compensation and benefits arrangements in the event that a Change of Control results in the Employee’s loss of equivalent employment.

In order to accomplish these objectives, the Board has caused the Employer to enter into this Agreement.

(a) “Effective Date” shall mean the first date during the Change of Control Period (as defined in Section 1.1(b)) on which a Change of Control occurs.

(b) “Change of Control Period” shall mean the period commencing on the date of this Agreement and ending on the second anniversary of the date the Employer gives notice to the Employee that the Change of Control Period shall be terminated.

The Employer hereby agrees to continue the Employee in its employ or in the employ of its affiliated companies, and the Employee hereby agrees to remain in the employ of the Employer or its affiliated companies, in accordance with the terms and provisions of this Agreement, for the period commencing on the Effective Date and continuing until terminated pursuant to paragraph 4 of this Agreement (the “Employment Period”).

During the Employment Period, the Employee’s position, authority, duties and responsibilities shall be at least reasonably commensurate in all material respects with the most significant of those held, exercised and assigned at any time during the 90-day period immediately preceding the Effective Date.

If prior to the Effective Date the Employee’s employment with the Employer or its affiliated companies terminates, then the Employee shall have no further rights under this Agreement.

During the Employment Period, and excluding any periods of vacation and sick leave to which the Employee is entitled, the Employee will devote all of his professional productive time, ability, attention and effort to the business and affairs of the Employer and the discharge of the responsibilities assigned to him hereunder, and will use his best efforts to perform faithfully and efficiently such responsibilities.

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

The Employee shall receive an annual base salary (the “Annual Base Salary”), at least equal to the annual salary established by the Board prior to the Effective Date for the fiscal year in which the Effective Date occurs. The Annual Base Salary shall be paid in substantially equal installments and at the same intervals as the salaries of other officers of the Employer are paid.

Employee may be entitled to receive, in addition to the Annual Base Salary, an annual bonus in an amount to be determined by the Board of Directors of the Employer in its sole discretion.

During the Employment Period, the Employee shall be entitled to participate, subject to and in accordance with applicable eligibility requirements, in such fringe benefit programs as shall be provided to other executive employees of the Employer and its affiliated companies from time to time during the Employment Period by action of the Board (or any

person or committee appointed by the Board to determine fringe benefit programs and other emoluments).

During the Employment Period, the Employee shall be entitled to receive prompt reimbursement for all reasonable employment expenses incurred by him in accordance with the policies, practices and procedures of the Employer and its affiliated companies in effect for the employees of the Employer and its affiliated companies during the Employment Period or pursuant to an applicable travel policy.

Employment of the Employee during the Employment Period may be terminated as follows but, in any case, the nondisclosure and noncompetition provisions set forth in Section 4 of the Employment Agreement shall survive the termination of this Agreement and the termination of the Employee’s employment with the Employer:

Upon giving Notice of Termination (as defined below), the Employer may terminate the employment of the Employee with or without Cause (as defined in the Employment Agreement), and the Employee may terminate his employment for Good Reason (as defined below) or for any reason, at any time during the Employment Period.

This Agreement and the Employee’s employment during the Employment Period shall terminate automatically pursuant to Section 2.3 of the Employment Agreement upon the death or total disability of the Employee. The Employee and the Employer hereby acknowledge that the Employee’s presence and ability to perform the duties specified in Section 1.3 hereof is of the essence of this Agreement.

Any termination by the Employer or by the Employee during the Employment Period shall be communicated by Notice of Termination to the other party given within 30 days in accordance with Section 2.5 of the Employment Agreement. The term “Notice of Termination” shall mean a written notice which (a) indicates the specific termination provision in this Agreement relied upon and (b) to the extent applicable, sets forth in reasonable detail the facts and circumstances claimed to provide a basis for termination of the Employee’s employment under the provision so indicated. The failure by the Employer to set forth in the Notice of Termination any fact or circumstance which contributes to a showing of Cause shall not waive any right of the Employer hereunder or preclude the Employer from asserting such fact or circumstance in enforcing the Employer’s rights hereunder.

During the Employment Period, “Date of Termination” means (a) if the Employee’s employment is terminated by reason of death, at the end of the calendar month in which the Employee’s death occurs, and (b) in all other cases, five days after the date of personal delivery of or mailing of, as applicable, the Notice of Termination. The Employee’s employment and performance of services will continue during such five-day period; provided, however, that the Employer may, upon notice to the Employee and without reducing the Employee’s compensation during such period, excuse the Employee from any or all of his duties during such period.

In the event of termination of the Employee’s employment during the Employment Period, all compensation and benefits set forth in this Agreement shall terminate except as specifically provided in this Section 5.

If the Employer terminates the Employee’s employment other than for Cause or the Employee terminates his employment for Good Reason prior to the end of the Employment Period, the Employee shall be entitled to:

(a) Receive payment of the following accrued obligations (the “Accrued Obligations”):

(i) the Employee’s Annual Base Salary through the Date of Termination to the extent not theretofore paid;

(ii) 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 in the current fiscal year through the Date of Termination, and the denominator of which is 365; and

(iii) any compensation previously deferred by the Employee (together with accrued interest or earnings thereon, if any) as such deferred compensation becomes payable under the deferral plan, and any accrued vacation pay, in each case to the extent not theretofore paid; and

(b) an amount as separation pay equal to the Employee’s Annual Base Salary.

If the Employee’s employment shall be terminated by the Employer for Cause as defined in the Employment Agreement or by the Employee for other than Good Reason

during the Employment Period, this Agreement shall terminate without further obligation to the Employee other than the obligation to pay to the Employee his Annual Base Salary through the Date of Termination plus the amount of any compensation previously deferred by the Employee (as such deferred compensation becomes payable under the deferral plan), in each case to the extent theretofore unpaid.

If the Employee’s employment is terminated by reason of the Employee’s death or total disability during the Employment Period, this Agreement shall terminate automatically without further obligations to the Employee or his legal representatives under this Agreement, other than for payment of Accrued Obligations (which shall be paid to the Employee’s estate or beneficiary, as applicable in the case of the Employee’s death).

Payments under Section 5.1(a) shall be paid to the Employee in a lump sum in cash within 30 days of the Date of Termination. Payments under Section 5.1(b) shall be paid to Employee at regular scheduled payroll intervals over the twelve (12) month period following the Date of Termination.

For purposes of this Agreement, “Good Reason” means any of the following events or conditions and the failure to cure such event or condition within 20 days after receipt of written notice from Employee:

(a) The assignment to the Employee of any duties inconsistent in any material respect with the Employee’s position, authority, duties or responsibilities as contemplated by Section 1.3 hereof or any other action by the Employer which results in a diminution in such position, authority, duties or responsibilities, excluding for this purpose an isolated and inadvertent action not taken in bad faith and which is remedied by the Employer promptly after receipt of notice thereof given by the Employee, and further excluding reasonable changes in particular duties and reporting responsibilities which may result from the 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 the Employee’s position, authority, duties or responsibilities;

(b) Any failure by the Employer to comply with any of the provisions of Section 3 hereof, other than an isolated and inadvertent failure not occurring in bad faith and which is remedied by the Employer promptly after receipt of notice thereof given by the Employee;

(c) Any failure by the Employer to comply with and satisfy Section 7 of the Employment Agreement, provided that the Employer’s successor has received at least ten days’ prior written notice from the Employer or the Employee of the requirements of Section 7 thereof;

(d) Any purported termination of the Employee’s employment that is not in accordance with the definition of Cause under the Employment Agreement; or

(e) A relocation of the Employer’s principal executive offices to a location more than 50 miles from the Seattle metropolitan area, or the Employer’s requirement that the Employee be based anywhere other than within 50 miles of the Seattle metropolitan area, except for required travel on the Employer’s business to an extent substantially consistent with the Employee’s position, duties and responsibilities.

In order to induce the Employer to enter into this Agreement, the Employee represents and warrants to the Employer as follows:

The Employee represents that neither the execution nor the performance of this Agreement by the Employee will violate or conflict in any way with any other agreement by which the Employee may be bound.

The Employee hereby acknowledges and reaffirms the Employee Proprietary Information and Inventions Agreement previously executed by Employee on the date hereof and Employee’s obligations under Section 4 of the Employment Agreement.

It is intended that any amounts or benefits payable under this Agreement and the Employer’s and the Employee’s exercise of authority or discretion hereunder shall comply with the provisions of Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”), and the treasury regulations or other guidance relating thereto so as not to subject the Employee to the payment of interest and tax penalties which may be imposed under Code Section 409A, and to maintain, to the maximum extent possible, the compensation and benefit levels of this Agreement. In furtherance of this interest, to the extent that any regulations or other guidance issued under Code Section 409A after the Effective Date would result in the Employee being subject to payment of interest or tax penalties under Code Section 409A, the parties agree to amend this Agreement if such amendment will, or reasonably may (based on the determination of the Employer), bring this Agreement into compliance with Code Section 409A.

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

APPENDIX A TO

CHANGE OF CONTROL AGREEMENT

For purposes of this Agreement, a “Change of Control” shall mean:

(a) A “Board Change” which, for purposes of this Agreement, shall have occurred if individuals who, as of the date of this Agreement, constitute the Board (the “Incumbent Board”) cease for any reason to constitute at least a majority of the Board; provided, however, that any individual becoming a director subsequent to the date hereof whose election, or nomination for election by the Company’s shareholders, was approved by a vote of at least a majority of the directors then comprising the Incumbent Board shall be considered as though such individual were a member of the Incumbent Board, but excluding for this purpose, any such individual whose initial assumption of office occurs as a result of either an actual or threatened election contest (as such terms are used in Rule 14a-11 of Regulation 14A promulgated under the Securities Exchange Act of 1934, as amended (the “Exchange Act”)) or other actual or threatened solicitation of proxies or consents by or on behalf of a Person (as hereinafter defined) other than the Board; or

(b) The acquisition by any individual, entity or group (within the meaning of Section 13(d)(3) or 14(d)(2) of the Exchange Act) (a “Person”) of beneficial ownership (within the meaning of Rule 13d-3 promulgated under the Exchange Act) of (i) 20% or more of either (A) the then outstanding shares of Common Stock of the Employer (the “Outstanding Employer Common Stock”) or (B) the combined voting power of the then outstanding voting securities of the Employer entitled to vote generally in the election of directors (the “Outstanding Employer Voting Securities”), in the case of either (A) or (B) of this clause (i), which acquisition is not approved in advance by a majority of the Incumbent Directors, or (ii) 33% or more of either (A) the Outstanding Employer Common Stock or (B) the Outstanding Employer Voting Securities, in the case of either (A) or (B) of this clause (ii), which acquisition is approved in advance by a majority of the Incumbent Directors; provided, however, that the following acquisitions shall not constitute a Change of Control: (w) any acquisition directly from the Employer or in connection with an offering of the Employer pursuant to a registration statement filed with and declared effective by the Securities and Exchange Commission, (x) any acquisition by the Employer, (y) any acquisition by any employee benefit plan (or related trust) sponsored or maintained by the Employer or any corporation controlled by the Employer or (z) any acquisition by any corporation pursuant to a reorganization, merger or consolidation, if, following such reorganization, merger or consolidation, the conditions described in clauses (i), (ii) and (iii) of subsection (c) of this Appendix A are satisfied; or

(c) Consummation of a reorganization, merger or consolidation approved by the stockholders of the Employer, in each case, unless, immediately following such reorganization, merger or consolidation, (i) more than 60% of, respectively, the then outstanding shares of common stock of the corporation resulting from such reorganization, merger or consolidation and the combined voting power of the then outstanding voting securities of such corporation entitled to vote generally in the election of directors is then

beneficially owned, directly or indirectly, by all or substantially all the individuals and entities who were the beneficial owners, respectively, of the Outstanding Employer Common Stock and the Outstanding Employer Voting Securities immediately prior to such reorganization, merger or consolidation in substantially the same proportion as their ownership immediately prior to such reorganization, merger or consolidation of the Outstanding Employer Common Stock and the Outstanding Employer Voting Securities, as the case may be, (ii) no Person (excluding the Employer, any employee benefit plan (or related trust) of the Employer or such corporation resulting from such reorganization, merger or consolidation and any Person beneficially owning, immediately prior to such reorganization, merger or consolidation, directly or indirectly, 33% or more of the Outstanding Employer Common Stock or the Outstanding Voting Securities, as the case may be) beneficially owns, directly or indirectly, 33% or more of, respectively, the then outstanding shares of common stock of the corporation resulting from such reorganization, merger or consolidation or the combined voting power of the then outstanding voting securities of such corporation entitled to vote generally in the election of directors, and (iii) at least a majority of the members of the board of directors of the corporation resulting from such reorganization, merger or consolidation were members of the Board at the time of the execution of the initial agreement providing for such reorganization, merger or consolidation; or

(d) Consummation of the following events approved by the stockholders of the Employer (i) a complete liquidation or dissolution of the Employer or (ii) the sale or other disposition of all or substantially all the assets of the Employer, other than to a corporation with respect to which immediately following such sale or other disposition, (A) more than 60% of, respectively, the then outstanding shares of common stock of such corporation and the combined voting power of the then outstanding voting securities of such corporation entitled to vote generally in the election of directors is then beneficially owned, directly or indirectly, by all or substantially all the individuals and entities who were the beneficial owners, respectively, of the Outstanding Employer Common Stock and the Outstanding Employer Voting Securities immediately prior to such sale or other disposition in substantially the same proportion as their ownership, immediately prior to such sale or other disposition, of the Outstanding Employer Common Stock and the Outstanding Employer Voting Securities, as the case may be, (B) no Person (excluding the Employer, any employee benefit plan (or related trust) of the Employer or such corporation and any Person beneficially owning, immediately prior to such sale or other disposition, directly or indirectly, 33% or more of the Outstanding Employer Common Stock or the Outstanding Employer Voting Securities, as the case may be) beneficially owns, directly or indirectly, 33% or more of, respectively, the then outstanding shares of common stock of such corporation and the combined voting power of the then outstanding voting securities of such corporation entitled to vote generally in the election of directors and (C) at least a majority of the members of the board of directors of such corporation were approved by a majority of the members of the Incumbent Board at the time of the execution of the initial agreement or action of the Board providing for such sale or other disposition of assets of the Employer.

Notwithstanding the foregoing, there shall not be a Change of Control if, in advance of such event, the Employee agrees in writing that such event shall not constitute a Change of Control.