Exhibit 5.1

[PERKINS COIE LETTERHEAD]

November 25, 2008

Coinstar, Inc.
1800 114th Avenue S.E.
Bellevue, WA 98004

Re: Registration Statement on Form S-3 Filed by Coinstar, Inc.

Ladies and Gentlemen:

     We have acted as counsel to Coinstar, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), and the rules and regulations promulgated thereunder (the “Rules”), of a registration statement on Form S-3, (the “Registration Statement”) for the registration of the sale from time to time of:

     (a) shares of the Company’s common stock, par value $0.001 per share (the “Common Stock”),

     (b) debt securities of the Company, which may be either senior debt securities or subordinated debt securities (the “Debt Securities”),

     (c) convertible debt securities of the Company, which may be either convertible senior debt securities or convertible subordinated debt securities (the “Convertible Debt Securities”),

     (d) stock purchase contracts for the purchase of Common Stock of the Company (“Stock Purchase Contracts”), and

     (e) stock purchase units consisting of one or more Stock Purchase Contracts and either Debt Securities, Convertible Debt Securities or debt obligations of third parties or any combination of such securities (the “Stock Purchase Units,” and together with the Common Stock, Debt Securities, Convertible Debt Securities, and Stock Purchase Contracts, collectively, the “Securities”).

     The Company has informed us that the Securities will be sold or delivered on a delayed or continuous basis from time to time as set forth in the Registration Statement (and any amendments thereto), the prospectus contained therein and any prospectus supplement. We understand that prior to the sale of any Securities under the Registration Statement, the Company

Coinstar, Inc.
November 25, 2008
Page 2

will afford us an opportunity to review the operative documents pursuant to which such Securities are to be sold and will file the applicable amendment to the Registration Statement (which may include as an exhibit an amendment to this opinion) or prospectus supplement as we may reasonably consider necessary or appropriate by reason of the terms of the sale of such Securities.

     In each case, except as otherwise set forth in the applicable amendment to the Registration Statement or prospectus supplement: (a) any Common Stock will be issued under the Company’s Amended and Restated Certificate of Incorporation, as amended from time to time; (b) any Debt Securities will be issued in one or more series pursuant to an applicable debt indenture (together with any supplemental indentures, a “Debt Indenture”) entered into between the Company and a trustee thereunder (the “Debt Trustee”) in a form filed as an exhibit to a post-effective amendment to the Registration Statement or incorporated by reference therein; (c) any Convertible Debt Securities will be issued in one or more series pursuant to an applicable convertible debt indenture (together with any supplemental indentures, a “Convertible Debt Indenture”) entered into between the Company and a trustee thereunder (the “Convertible Debt Trustee”) in a form filed as an exhibit to a post-effective amendment to the Registration Statement or incorporated by reference therein; (d) any Stock Purchase Contracts will be issued pursuant to one or more stock purchase agreements (each a “Stock Purchase Agreement”) entered into between the Company and a financial institution identified therein as the purchase contract agent (the “Purchase Contract Agent”) in a form filed as an exhibit to a post-effective amendment to the Registration Statement or incorporated by reference therein; and (e) any Stock Purchase Units will be issued pursuant to one or more stock purchase unit agreements (each a “Stock Purchase Unit Agreement”) to be entered into among the Company and a financial institution identified therein as the purchase unit agent (the “Purchase Unit Agent”) in a form filed as an exhibit to a post-effective amendment to the Registration Statement or incorporated by reference therein.

     As part of the corporate actions taken and to be taken in connection with the issuance and sale of the Securities (the “corporate proceedings”), the Board or a committee thereof or, in the case of Debt Securities, certain authorized officers of the Company as authorized by the Board will, before the Securities are issued and sold under the Registration Statement, authorize the issuance and approve the terms of any Securities to be issued and sold from time to time under the Registration Statement, and such applicable corporate proceedings shall be in full force and effect at any such issuance and sale.

     In our capacity as counsel to the Company, we have examined or are otherwise familiar with the Company’s Amended and Restated Certificate of Incorporation, as amended, and Amended and Restated Bylaws, the Registration Statement, such of the corporate proceedings as have occurred as of the date hereof, and such other documents, records and instruments as we have deemed necessary for the purposes of this opinion. In such examination, we have assumed

Coinstar, Inc.
November 25, 2008
Page 3

the following: (i) the authenticity of original documents and the genuineness of all signatures; (ii) the conformity to the originals of all documents submitted to us as copies; and (iii) the truth, accuracy and completeness of the information, representations and warranties contained in the records, documents, instruments and certificates we have reviewed. For purposes of the opinions expressed below, we also assume that: (a) the Registration Statement and any amendments or prospectus supplements relating thereto shall have become and be effective pursuant to timely filings under the Securities Act; (b) a prospectus supplement describing each class and series of Securities offered pursuant to the Registration Statement, to the extent required by applicable law and the Rules, will be timely filed with the Commission; (c) with respect to the opinions in Paragraphs 2, 4, 6 and 8 below, the Company, the Debt Trustee, the Convertible Debt Trustee, the Purchase Contract Agent or the Purchase Unit Agent, as applicable, will have complied with the terms and conditions of the Debt Indenture, the Convertible Debt Indenture, the Stock Purchase Agreement or the Stock Purchase Unit Agreement, as applicable, including, the creation, authentication and delivery of any supplemental indenture to an indenture; (d) any Securities issuable upon conversion, exchange, or exercise of any of the other Securities, will have been duly authorized and reserved for issuance (in each case within the limits of the then remaining authorized but unreserved and unissued amounts of such Securities), and duly executed and delivered and validly issued, as the case may be; and (e) at the time of issuance and sale of any of the Securities, the terms of the Securities, and their issuance and sale, will have been established so as not to violate any applicable law or result in a default under or a breach of any agreement or instrument binding upon the Company and so as to comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company. Based on and subject to the foregoing, we are of the opinion that:

1.	The Common Stock, when issued, sold and delivered in the manner and for the consideration stated in the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and as contemplated by the applicable corporate proceedings, will be validly issued, fully paid and nonassessable.
2.	When a Debt Indenture has been duly authorized, executed and delivered by the Company and qualified under the Trust Indenture Act of 1939, as amended (the “Trust Indenture Act”), and assuming due authorization, execution and delivery by the Debt Trustee, such Debt Indenture will constitute a valid and legally binding obligation of the Company, enforceable against the Company in accordance with its terms.
3.	When (a) the applicable Debt Securities have been duly authorized by the Company, (b) the final terms of the applicable Debt Securities have been duly established and approved and (c) the applicable Debt Securities have been duly executed by the Company and authenticated by the Debt Trustee in accordance

Coinstar, Inc.
November 25, 2008
Page 4

	with the applicable Debt Indenture and delivered to and paid for by the purchasers thereof as contemplated by the Registration Statement (including any amendments thereto), and any prospectus supplements relating thereto, and as contemplated by the applicable corporate proceedings, such Debt Securities will constitute valid and legally binding obligations of the Company, enforceable against the Company in accordance with the terms thereof and will be entitled to the benefits of the applicable Debt Indenture.
4.	When a Convertible Debt Indenture has been duly authorized, executed and delivered by the Company and qualified under the Trust Indenture Act, and assuming due authorization, execution and delivery by the Convertible Debt Trustee, such Convertible Debt Indenture will constitute a valid and legally binding obligation of the Company, enforceable against the Company in accordance with its terms.
5.	When (a) the applicable Convertible Debt Securities have been duly authorized by the Company, (b) the final terms of the applicable Convertible Debt Securities have been duly established and approved and (c) the Convertible Debt Securities have been duly executed by the Company and authenticated by the Convertible Debt Trustee in accordance with the applicable Convertible Debt Indenture and delivered to and paid for by the purchasers thereof as contemplated by the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and as contemplated by the applicable corporate proceedings, such Convertible Debt Securities will constitute valid and legally binding obligations of the Company, enforceable against the Company in accordance with the terms thereof and will be entitled to the benefits of the applicable Convertible Debt Indenture.
6.	When a Stock Purchase Agreement as contemplated by the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and by the applicable corporate proceedings, has been duly authorized, executed and delivered by the Company, and assuming due authorization, execution and delivery by the Purchase Contract Agent, such Stock Purchase Agreement will constitute a valid and legally binding obligation of the Company, enforceable against the Company in accordance with its terms.
7.	When (a) the applicable Stock Purchase Contracts have been duly authorized by the Company, (b) the final terms of the Stock Purchase Contracts have been duly established and approved, and (c) the applicable Stock Purchase Contracts have been duly executed by the Company and countersigned or authenticated in accordance with the applicable Stock Purchase Agreement and delivered to and

Coinstar, Inc.
November 25, 2008
Page 5

	paid for by the purchasers thereof as contemplated by the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and as contemplated by the applicable corporate proceedings, such Stock Purchase Contracts will constitute valid and legally binding obligations of the Company, enforceable against the Company in accordance with their terms.
8.	When a Stock Purchase Unit Agreement as contemplated by the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and by the applicable corporate proceedings, has been duly authorized, executed and delivered by the Company, and assuming due authorization, execution and delivery by the Purchase Unit Agent, such Stock Purchase Unit Agreement will constitute a valid and legally binding obligation of the Company, enforceable against the Company in accordance with its terms.
9.	When (a) the applicable Stock Purchase Units have been duly authorized by the Company, (b) the final terms of the Stock Purchase Units have been duly established and approved, and (c) the applicable Stock Purchase Units have been duly executed by the Company and countersigned or authenticated in accordance with the applicable Stock Purchase Unit Agreement and delivered to and paid for by the purchasers thereof as contemplated by the Registration Statement (including any amendments thereto) and any prospectus supplements relating thereto, and as contemplated by the applicable corporate proceedings, such Stock Purchase Units will constitute valid and legally binding obligations of the Company, enforceable against the Company in accordance with their terms.

     The foregoing opinions are subject to the following exclusions and qualifications:

     a. Our opinions are as of the date hereof and we have no responsibility to update this opinion for events and circumstances occurring after the date hereof or as to facts relating to prior events that are subsequently brought to our attention. This opinion is limited to the laws, including the rules and regulations, as in effect on the date hereof, and we disavow any undertaking to advise you of any changes in law.

     b. We express no opinion as to enforceability of any right or obligation to the extent such right and obligation is subject to and limited by (i) the effect of bankruptcy, insolvency, reorganization, receivership, conservatorship, arrangement, moratorium, fraudulent transfer or other laws affecting or relating to the rights of creditors generally, (ii) rules governing the availability of specific performance, injunctive relief or other equitable remedies and general principles of equity, regardless of whether arising prior to, or after, the date hereof or considered in a proceeding in equity or at law or (iii) the effect of federal and state securities laws and principles of public policy on the rights of indemnity and contribution.

Coinstar, Inc.
November 25, 2008
Page 6

     c. We are qualified to practice law in the State of Washington and do not express any opinions herein concerning any laws other than the laws in their current forms of the State of Washington, the Delaware General Corporation Law and applicable provisions of the Delaware Constitution and reported judicial decisions interpreting such Delaware laws, and the federal securities laws of the United States of America, and we express no opinion with respect to the laws of any other jurisdiction.

     This opinion letter is rendered solely for your benefit in connection with the offer and sale of the Securities and may not be relied upon, quoted or used by any other person or entity or for any other purpose without our prior written consent.

     We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and any amendments thereto, including any and all post-effective amendments, and to the reference to our firm in the prospectus and any prospectus supplements relating thereto under the heading “Legal Matters.” In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or related Rules.

Very truly yours,
 

/s/ PERKINS COIE LLP