Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

The Board of Directors
Coinstar, Inc.:

We consent to the incorporation by reference in the registration statements (Nos. 333-30985, 333-89975, 333-63108, 333-98297, 333-100870, 333-120547, 333-127293, 333-147087,and 333-161134) on Form S-8 and registration statements (Nos. 333-123326, 333-130000, 333-155691, 333-157552, and 333-157553) on Form S-3 of Coinstar, Inc. of our reports dated February 23, 2009 except as to notes 11 and 19, which are as of August 24, 2009, with respect to the consolidated balance sheets of Coinstar, Inc. as of December 31, 2008 and 2007, and the related consolidated statements of operations, stockholders’ equity and comprehensive income (loss) and cash flows for each of the years in the three-year period ended December 31, 2008, and the effectiveness of internal control over financial reporting as of December 31, 2008, which reports appear in the Form 8-K of Coinstar, Inc. dated August 24, 2009.

The audit report refers to the Company’s adoption and the retrospective application of the presentation and disclosure requirements of Statement of Financial Accounting Standards No. 160, Non-controlling Interests in Consolidated Financial Statements.

/s/ KPMG LLP

Seattle, Washington
August 24, 2009