Exhibit 10.5

CHANGE OF CONTROL AGREEMENT

This Change of Control Agreement (this “Agreement”), dated as of January 2, 2013 is between Coinstar, Inc. (the “Employer”), and Galen C. Smith (the “Employee”).

The Compensation Committee (the “Committee”) of the Board of Directors (the “Board”) of the Employer 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 Committee 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 Committee 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 ending two years after such date. (the “Employment Period”).

During the Employment Period, the Employee’s duties, authority 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.

-1-

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).

-2-

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:

Upon giving Notice of Termination (as defined below), the Employer may terminate the employment of the Employee with or without Cause (as defined below), 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 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. 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, the later of (i) five days after the date of personal delivery of or mailing of, as applicable, the Notice of Termination, and (ii) the date on which the Employee separates from service, within the meaning of Section 409A(a)(2)(A)(i) of the Internal Revenue Code of 1986, as amended (the “Code”).

-3-

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.

(c) If, as a result of the termination of the Employee’s employment, the Employee and the Employee’s spouse and dependent children are eligible for and timely (and properly) elect to continue coverage under the Employers’ group health plans(s) in accordance with Code Section 4980B(f) (“COBRA”), the Employer shall pay the premium for such coverage for a period of twelve (12) months following the Date of Termination or until the Employee is no longer entitled to COBRA continuation coverage under the Employer’s group health plan(s), whichever period if shorter.

-4-

If the Employee’s employment shall be terminated by the Employer for Cause 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), 5.2 and 5.3 (other than payments of deferred compensation, which shall be paid in accordance with the provisions of the plan under which such compensation was deferred) 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 in twelve (12) equal monthly installments, beginning with the month following the month containing the Date of Termination and continuing for eleven (11) consecutive months thereafter. For purposes of Code Section 409A, each installment payable pursuant to Section 5.1(b) and this Section 5.4 shall be treated as a separate payment.

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

(i) A diminution in the Employee’s Annual Base Salary;

(ii) A diminution in the Employee’s authority, duties or responsibilities as contemplated by Section 1.3 hereof, excluding for this purpose 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 authority, duties or responsibilities;

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

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

(b) Notwithstanding any provision in this Agreement to the contrary, termination of employment by the Employee will not be for Good Reason unless (i) the Employee notifies the Employer in writing of the occurrence or existence of the event or condition which the 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) the 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) the Employee actually terminates employment within 90 days after the expiration of the Remedial Period and before the Employer remedies such event or condition. If the Employee terminates employment before the expiration of the Remedial Period or after the Employer remedies the event or condition (even if after the end of the Remedial Period), then the Employee’s termination will not be considered to be for Good Reason.

For purposes of this Agreement, “Cause” means the occurrence of one or more of the following events:

(a) Failure or refusal to carry out the lawful duties of the Employee or any directions of the Board which are consistent with the duties to be performed by the Employee;

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

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

(d) Any material violation of the confidentiality, non-competition and/or non-solicitation provisions to which the Employee is bound.

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.

The Employee hereby acknowledges that as of the date of this Agreement, this Agreement sets forth the entire understanding between the Employee and the Employer regarding the subject matter herein and supersedes all prior oral or written agreements on the subject.

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. The 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 the Employee is a “specified employee,” within the meaning of Code Section 409A(a)(2)(B)(i), when the Employee 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.

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 Employer’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.