Exhibit 10.4

COINSTAR, INC.

NOTICE OF RESTRICTED STOCK AWARD TO CEO, COO OR CFO

1997 AMENDED AND RESTATED EQUITY INCENTIVE PLAN

Date:

To:

You have been granted an award of restricted stock (the “Restricted Stock Award”) by Coinstar, Inc. (the “Company”). This Restricted Stock Award is subject to the terms of the enclosed Restricted Stock Award Agreement and the Company’s 1997 Amended and Restated Equity Incentive Plan (the “Plan”). Except as expressly provided otherwise in the Restricted Stock Award Agreement, the Restricted Stock Award is limited by and subject to the express terms and conditions of the Plan. Defined terms in the Plan shall have the same meaning in this Notice of Restricted Stock Award, except where the context otherwise requires. By accepting this Restricted Stock Award, you accept it subject to the terms of this Notice of Restricted Stock Award and the enclosed Restricted Stock Award Agreement.

The basic terms of the Restricted Stock Award are summarized as follows:

COINSTAR, INC.

RESTRICTED STOCK AWARD AGREEMENT FOR AWARDS TO CEO, COO OR CFO

Pursuant to your Notice of Restricted Stock Award, (the “Grant Notice”) the Company has awarded you an award of restricted stock (the “Restricted Stock Award”) under its 1997 Amended and Restated Equity Incentive Plan (the “Plan”) for the number of shares of the Company’s Common Stock indicated in your Grant Notice. The Grant Notice, the Plan and this Restricted Stock Award Agreement (this “Agreement”) govern the terms of the award. Capitalized terms not explicitly defined in this Agreement but defined in the Plan shall have the same definitions as in the Plan.

1. Vesting

Shares that have vested and are no longer subject to forfeiture according to the vesting schedule set forth in the Grant Notice are referred to herein as “Vested Shares.” Shares that are not vested and remain subject to forfeiture under the preceding schedule are referred to herein as “Unvested Shares.” The Unvested Shares will vest (and to the extent so vested cease to be Unvested Shares remaining subject to forfeiture) in accordance with the vesting schedule set forth in the Grant Notice. Collectively, the Unvested Shares and the Vested Shares are referred to herein as the “Shares.”

2. Transfer Restrictions

Any sale, transfer, assignment, encumbrance, pledge, hypothecation, conveyance in trust, gift, transfer by bequest, devise or descent, or other transfer or disposition of any kind, whether voluntary or by operation of law, directly or indirectly, of Unvested Shares shall be strictly prohibited and void, except by will or the laws of descent and distribution.

3. Status of Participant

You will be recorded as a shareholder of the Company with respect to the Shares and will have all rights of a shareholder with respect to the Shares, including voting rights; provided, however, that you will not accrue or be entitled to any dividends with respect to Unvested Shares.

4. Securities Law Compliance

4.1 You represent and warrant that you (a) have been furnished with all information which you deem necessary to evaluate the merits and risks of receipt of the Shares, (b) have had the opportunity to ask questions and receive answers concerning the information received about the Shares and the Company, and (c) have been given the opportunity to obtain any additional information you deem necessary to verify the accuracy of any information obtained concerning the Shares and the Company.

4.2 You hereby agree that you will in no event sell or distribute all or any part of the Shares unless (a) there is an effective registration statement under the Securities Act of 1933, as amended (the “Securities Act”) and applicable state securities laws covering any such transaction involving the Shares or (b) the Company receives an opinion of your legal counsel (concurred in by legal counsel for the Company) stating that such transaction is exempt from registration or the Company otherwise satisfies itself that such transaction is exempt from registration. You understand that the Company has no obligation to you to register the Shares with the Securities and Exchange Commission and has not represented to you that it will so register the Shares.

4.3 You confirm that you have been advised, prior to your receipt of the Shares, that neither the offering of the Shares nor any offering materials have been reviewed by any administrator under the Securities Act or any other applicable securities act.

4.4 You hereby agree to indemnify the Company and hold it harmless from and against any loss, claim or liability, including attorneys’ fees or legal expenses, incurred by the Company as a result of any breach by you of, or any inaccuracy in, any representation, warranty or statement made by you in this Agreement or the breach by you of any terms or conditions of this Agreement.

5. Termination of Employment; Company Transaction

5.1 Termination of Employment

Except as provided in Section 5.2 below, in the event your Continuous Status as an Employee, Director or Consultant terminates for any reason, including without limitation, your voluntary termination, termination by the Company, or the occurrence of your death, disability or retirement, the Unvested Shares shall be forfeited by you without payment of any further consideration to you.

5.2 Company Transaction

In the event of a merger, reorganization or sale of substantially all of the assets of the Company (a “Company Transaction”), then (a) if the performance goals set forth in the Grant Notice have not been met, any Unvested Shares shall be forfeited by you without payment of any further consideration to you and (b) if the performance goals set forth in the Grant Notice have been met, to the extent permitted by applicable law (i) any surviving corporation or a parent of such surviving corporation shall assume any vested or unvested Shares outstanding under the Plan or shall substitute similar Shares for those outstanding under the Plan, or (ii) such Shares shall continue in full force and effect. Any Shares that are assumed or replaced in connection with such a Company Transaction shall automatically become fully vested with respect to 100% of the unvested portion of the Shares (the forfeiture or repurchase provisions to which such Unvested Shares may be subject shall lapse to the same extent) in the event that your employment or service relationship with the successor company should terminate (i) in connection with the Company Transaction or (ii) subsequently within two (2) years following such Company Transaction, unless such employment or service relationship is

terminated by the successor company for Cause or by you voluntarily without Good Reason. In the event any surviving corporation or its parent refuses to assume or continue such Shares, or to substitute similar Shares for those outstanding under the Plan, then, with respect to Shares held by you if then performing services as Employee, Director or Consultant the vesting of such Unvested Shares shall be accelerated so that the restrictions on the Shares will lapse and the Shares will no longer be subject to forfeiture.

“Good Reason” means the occurrence of any of the following events or conditions and the failure of the successor company to cure such event or condition within 30 days after receipt of written notice from you:

(a) a change in your status, position or responsibilities (including reporting responsibilities) that, in your reasonable judgment, represents a substantial reduction in your status, position or responsibilities as in effect immediately prior thereto; the assignment to you of any duties or responsibilities that, in your reasonable judgment, are materially inconsistent with such status, title, position or responsibilities; or any removal from or failure to reappoint or reelect you to any of such positions, except in connection with the termination of your employment for Cause, as a result of you disability or death, or by you other than for Good Reason;

(b) a reduction in your annual base salary;

(c) the successor company’s requiring you (without your consent) to be based at any place outside a 50-mile radius of your place of employment prior to a Company Transaction, except for reasonably required travel on the successor company’s business that is not materially greater than such travel requirements prior to the Company Transaction;

(d) the successor company’s failure to (i) continue in effect any material compensation or benefit plan (or the substantial equivalent thereof) in which you were participating at the time of a Company Transaction, including, but not limited to, the Plan, or (ii) provide you with compensation and benefits substantially equivalent (in terms of benefit levels and/or reward opportunities) to those provided for under each material employee benefit plan, program and practice as in effect immediately prior to the Company Transaction;

(e) any material breach by the successor company of its obligations to you under the Plan or any substantially equivalent plan of the successor company; or

(f) any purported termination of your employment or service relationship for Cause by the successor company that is not in accordance with the definition of Cause under the Plan.

“Cause,” unless otherwise defined in an employment or services agreement between the Company and you, means dishonesty, fraud, misconduct, unauthorized use or disclosure of confidential information or trade secrets, or conviction or confession of a crime punishable by law (except minor violations), in each case as determined by the Plan Administrator, and its determination shall be conclusive and binding.

6. Section 83(b) Election for Restricted Stock Award; Independent Tax Advice

You understand that under Section 83(a) of the Internal Revenue Code of 1986 (the “Code”), the fair market value of the Unvested Shares on the date the forfeiture restrictions lapse will be taxed, on the date such forfeiture restrictions lapse, as ordinary income subject to payroll and withholding tax and tax reporting, as applicable. For this purpose, the term “forfeiture restrictions” means the right of the Company to receive back any Unvested Shares as provided in this Agreement. You understand that you may elect under Section 83(b) of the Code to be taxed at ordinary income rates on the fair market value of the Unvested Shares at the time they are acquired, rather than when and as the Unvested Shares cease to be subject to the forfeiture restrictions. Such election (an “83(b) Election”) must be filed with the Internal Revenue Service within 30 days from the grant date of the Restricted Stock Award.

You understand that there are significant risks associated with the decision to make and 83(b) Election. If you make an 83(b) Election and the Unvested Shares are subsequently forfeited to the Company, you will not be entitled to a deduction for any ordinary income previously recognized as a result of the 83(b) Election. If you make an 83(b) Election and the value of the Unvested Shares subsequently declines, the 83(b) Election may cause you to recognize more compensation income than you would have otherwise recognized. On the other hand, if the value of the Unvested Shares increases and you have not made an 83(b) Election, you may recognize more compensation income than you would have if you had made the election.

THE FORM FOR MAKING AN 83(b) ELECTION IS ATTACHED TO THIS AGREEMENT AS EXHIBIT B. YOU UNDERSTAND THAT, IF YOU DECIDE TO MAKE AN 83(b) ELECTION, IT IS YOUR RESPONSIBILITY TO FILE SUCH AN ELECTION WITH THE INTERNAL REVENUE SERVICE AND THAT FAILURE TO FILE SUCH AN ELECTION WITHIN THE 30-DAY PERIOD MAY RESULT IN THE RECOGNITION OF ORDINARY INCOME BY YOU AS THE FORFEITURE RESTRICTIONS LAPSE. You further understand that an additional copy of such election form should be filed with your federal income tax return for the calendar year in which the date of this Agreement falls. You acknowledge that the foregoing is only a summary of the federal income tax laws that apply to the award of the Shares under this Agreement and does not purport to be complete. YOU FURTHER ACKNOWLEDGE THAT THE COMPANY HAS DIRECTED YOU TO SEEK INDEPENDENT ADVICE REGARDING THE APPLICABLE PROVISIONS OF THE CODE AND THE INCOME TAX LAWS OF ANY MUNICIPALITY, STATE OR FOREIGN COUNTRY IN WHICH YOU MAY RESIDE.

You agree to execute and deliver to the Company with this Agreement a copy of the Acknowledgment and Statement of Decision Regarding Section 83(b) Election (the “Acknowledgment”) attached hereto as Exhibit A. You further agree that if you choose to make an 83(b) Election with the Internal Revenue Service, you will also deliver to the Company with this signed Agreement a signed copy of the 83(b) Election.

You acknowledge that determining the actual tax consequences to you of receiving or disposing of the Shares may be complicated. These tax consequences will depend, in part, on your specific situation and may also depend on the resolution of currently uncertain tax law and other variables not within the control of the Company. You are aware that you should consult a competent and independent tax advisor for a full understanding of the specific tax consequences to you of receiving or disposing of the Shares. Prior to executing this Agreement, you either have consulted with a competent tax advisor independent of the Company to obtain tax advice concerning the Shares in light of your specific situation or have had the opportunity to consult with such a tax advisor but have chosen not to do so.

7. Book Entry Registration of the Shares

The Company will issue the Shares by registering the Shares in book entry form with the Company’s transfer agent in your name and the applicable restrictions will be noted in the records of the Company’s transfer agent and in the book entry system. No certificate(s) representing all or a part of the Shares will be issued until the Shares become Vested Shares.

8. Stop-Transfer Notices

You understand and agree that, in order to ensure compliance with the restrictions referred to in this Agreement, the Company may issue appropriate “stop-transfer” instructions to its transfer agent, if any, and that, if the Company transfers its own securities, it may make appropriate notations to the same effect in its own records. The Company will not be required to (a) transfer on its books any Shares that have been sold or transferred in violation of the provisions of this Agreement or (b) treat as the owner of the Shares, or otherwise accord voting, dividend or liquidation rights to, any transferee to whom the Shares have been transferred in contravention of this Agreement.

9. Tax Withholding

As a condition to the removal of restrictions from your Vested Shares registered in book entry form with the Company’s transfer agent, you agree to make arrangements satisfactory to the Company for the payment of any federal, state, local or foreign withholding tax obligations that arise either upon receipt of the Shares or as the forfeiture restrictions on any Shares lapse. You may satisfy such withholding obligation by any of the following means or a combination thereof: (a) tendering a cash payment, (b) authorizing the Company to withhold shares from the shares of Common Stock otherwise issuable pursuant to the Restricted Stock Award (up to the employer’s minimum tax withholding rate) or (c) delivering to the Company already owned and unencumbered shares of Common Stock (up to the employer’s minimum required tax withholding rate to the extent the shares have been held for less than six months). Notwithstanding the previous sentence, you acknowledge and agree that the Company and any Affiliate has the right to deduct from payments of any kind otherwise due to you any federal, state, local or foreign taxes of any kind required by law to be withheld with respect to the Restricted Stock Award.

10. General Provisions

10.1 Notices

Whenever any notice is required or permitted hereunder, such notice must be in writing and personally delivered or sent by mail. Any notice required or permitted to be delivered hereunder shall be deemed to be delivered on the date on which it is personally delivered, or, whether actually received or not, on the third business day after it is deposited in the United States mail, certified or registered, postage prepaid, addressed to the person who is to receive it at the address that such person has theretofore specified by written notice delivered in accordance herewith. The Company or Participant may change, by written notice to the other, the address previously specified for receiving notices. Notices delivered to the Company shall be addressed as follows:

10.2 No Waiver

No waiver of any provision of this Agreement will be valid unless in writing and signed by the person against whom such waiver is sought to be enforced, nor will failure to enforce any right hereunder constitute a continuing waiver of the same or a waiver of any other right hereunder.

10.3 Undertaking

You hereby agree to take whatever additional action and execute whatever additional documents the Company may deem necessary or advisable in order to carry out or effect one or more of the obligations or restrictions imposed on either you or the Shares pursuant to the express provisions of this Agreement.

10.4 Entire Contract

This Agreement, the Grant Notice, the Plan and the Company’s Policy on Reimbursement of Incentive Payments constitute the entire contract between the parties hereto with regard to the subject matter hereof and supersede all prior oral or written agreements on the subject. This Agreement is made pursuant to the provisions of the Plan and will in all respects be construed in conformity with the express terms and provisions of the Plan.

10.5 Successors and Assigns

The provisions of this Agreement will inure to the benefit of, and be binding on, the Company and its successors and assigns and you and your legal representatives, heirs, legatees, distributees, assigns and transferees by operation of law, whether or not any such person will have become a party to this Agreement and agreed in writing to join herein and be bound by the terms and conditions hereof.

10.6 Counterparts

This Agreement may be executed in two or more counterparts, each of which will be deemed an original, but which, upon execution, will constitute one and the same instrument.

10.7 Governing Law

The provisions of the Grant Notice and this Agreement shall be governed by the laws of the state of Washington, without giving effect to principles of conflicts of law.

11. Section 409A

Awards under the Plan are intended either to be exempt from the rules of Section 409A or to satisfy those rules, and shall be construed accordingly.

IN WITNESS WHEREOF, the parties have executed this Agreement dated as of             , 201    .

EXHIBIT A

ACKNOWLEDGMENT AND STATEMENT OF DECISION REGARDING SECTION 83(b) ELECTION

The undersigned, a recipient of      shares of common stock of Coinstar, Inc., a Delaware corporation (the “Company”), pursuant to a restricted stock award granted under the Company’s 1997 Amended and Restated Equity Incentive Plan (the “Plan”), hereby states as follows:

1. The undersigned acknowledges receipt of a copy of the Restricted Stock Award Agreement and the Plan relating to the offering of such shares. The undersigned has carefully reviewed the Plan and the Restricted Stock Award Agreement pursuant to which the award was granted.

2. The undersigned either (check and complete as applicable)

3. The undersigned hereby states that the undersigned has decided (check as applicable)

4. Neither the Company nor any subsidiary or representative of the Company has made any warranty or representation to the undersigned with respect to the tax consequences of the undersigned’s acquisition of shares under the Plan or of the making or failure to make an election pursuant to Section 83(b) of the Code or the corresponding provisions, if any, of applicable state law.

EXHIBIT B

ELECTION UNDER SECTION 83(b)

OF THE INTERNAL REVENUE CODE OF 1986

The undersigned taxpayer hereby elects, pursuant to Section 83(b) of the Internal Revenue Code, to include in taxpayer’s gross income for the current taxable year the amount of any compensation taxable to taxpayer in connection with taxpayer’s receipt of the property described below:

The undersigned has submitted a copy of this statement to the person for whom the services were performed in connection with the undersigned’s receipt of the above-described property. The undersigned is the person performing the services in connection with the transfer of said property.

The undersigned understands that the foregoing election may not be revoked except with the consent of the Commissioner of Internal Revenue.

DISTRIBUTION OF COPIES

Coinstar, Inc.

1800 114^th Avenue SE

Bellevue, WA 98004