Exhibit 99.2

COINSTAR, INC. ANNOUNCES 2011 FIRST QUARTER RESULTS

Solid Execution Drives Top and Bottom Line Growth

Company Announces National Rollout of Video Game Rentals

BELLEVUE, Wash.—April 28, 2011—Coinstar, Inc. (NASDAQ: CSTR) today announced financial results for the first quarter ended March 31, 2011.

“Strong growth in our redbox business and consistent performance in the Coin business delivered better-than-expected earnings in the first quarter,” said Paul Davis, chief executive officer of Coinstar, Inc. “The quarter was marked by solid execution across our businesses and the enhancements to operations are showing progress. In addition, I’m very pleased to announce our decision to rollout video games at redbox kiosks nationwide, which we believe will expand our user base by tapping into the growing video game rental market.”

Redbox will offer video game rentals alongside movies at more than 21,000 locations beginning in June.

First quarter financial highlights included:

“During the first quarter we made progress in driving improvements in our operations and in building scale by investing in infrastructure, while continuing to deliver profitable growth,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “We’re gaining traction as we’ve added more rigor to our processes and we will continue to monitor and refine as we progress through the year.”

Revenue for the first quarter of 2011 increased 31.2% to $424.1 million compared with the first quarter of 2010, driven primarily by growth in redbox (formerly DVD Services) revenue, which increased 37.7% to $362.3 million, and by Coin revenue which grew 2.4% to $61.4 million.

Operating income for the first quarter of 2011 was $31.4 million, which resulted in an operating margin of 7.4%, compared with operating income of $24.5 million and an operating margin of 7.6% in the first quarter of 2010. The decrease in operating margin percentage primarily reflects increased DVD product costs due in part to higher than optimal purchases of DVD titles.

Income from continuing operations for the first quarter of 2011 was $14.8 million, or diluted earnings per share from continuing operations of $0.46, compared with $9.2 million, or $0.30 per share, in the first quarter of 2010.

Net income for the first quarter of 2011, which includes both continuing and discontinued operations, was $8.5 million, or diluted earnings per share of $0.26. This compares with $6.4 million, or diluted earnings per share of $0.21, in the first quarter of 2010.

Net cash flows from operating activities from continuing operations was $60.0 million in the first quarter of 2011, compared with $59.5 million in the first quarter of 2010. Cash paid for capital expenditures for

continuing operations for the first quarter of 2011 was $38.5 million, compared with $31.5 million in the first quarter of 2010, reflecting increased investment in kiosks, as well as investment in corporate infrastructure. Free cash flow from continuing operations for the first quarter of 2011 was $21.5 million, compared with $28.0 million in the first quarter of 2010.

During the first quarter, Coinstar repurchased $13.3 million of common stock on the open market. In addition, the company announced a $50 million accelerated share repurchase (ASR) program, which is expected to close in the second quarter. As of the end of the first quarter, the company had a remaining total authorization to repurchase $11.5 million of Coinstar’s common stock.

Guidance

For the 2011 full year, Coinstar management updated guidance and now expects:

For the 2011 second quarter, Coinstar management expects:

Conference Call

Paul Davis and J. Scott Di Valerio will host a conference call today at 2:00 p.m. PDT (5:00 p.m. EDT) to review the first quarter results and discuss guidance. The conference call will be webcast live and archived on the Investor Relations section of Coinstar’s website at www.coinstarinc.com. A recording of the call will be available approximately two hours after the call ends through May 12, 2011, at 1-888-286-8010 or 1-617-801-6888, passcode 65266451.

About Coinstar, Inc.

Coinstar, Inc. (NASDAQ: CSTR) is a leading provider of automated retail solutions offering convenient services that make life easier for consumers and drive incremental traffic and revenue for retailers. The company’s core automated retail businesses include the well-known redbox^® self-service DVD rental and Coinstar^® self-service coin-counting brands. The company has approximately 31,800 DVD kiosks and 18,800 coin-counting kiosks in supermarkets, drug stores, mass merchants, financial institutions, convenience stores, and restaurants. For more information, visit www.coinstarinc.com.

Safe Harbor for Forward-Looking Statements

Certain statements in this press release are “forward-looking statements” within the meaning of the Private Securities Litigation Reform Act of 1995. The words “believe,” “estimate,” “expect,” “intend,” “anticipate,” “goals,” variations of such words, and similar expressions identify forward-looking statements, but their absence does not mean that the statement is not forward-looking. The forward-looking statements in this release include statements regarding Coinstar, Inc.’s anticipated growth and future operating results. Forward-looking statements are not guarantees of future performance and actual results may vary materially from the results expressed or implied in such statements. Differences may result from actions taken by Coinstar, Inc., as well as from risks and uncertainties beyond Coinstar, Inc.’s

control. Such risks and uncertainties include, but are not limited to, the termination, non-renewal or renegotiation on materially adverse terms of our contracts with our significant retailers and suppliers, payment of increased fees to retailers and suppliers, the inability to receive delivery of DVDs on the date of their initial release to the general public, or shortly thereafter, for home entertainment viewing, the effective management of our DVD inventory, the ability to attract new retailers, penetrate new markets and distribution channels and react to changing consumer demands, the ability to achieve the strategic and financial objectives for our entry into or expansion of new businesses, the ability to adequately protect our intellectual property, and the application of substantial federal, state, local and foreign laws and regulations specific to our business. The foregoing list of risks and uncertainties is illustrative, but by no means exhaustive. For more information on factors that may affect future performance, please review “Risk Factors” described in our most recent Annual Report on Form 10-K and Quarterly Report on Form 10-Q filed with the Securities and Exchange Commission. These forward-looking statements reflect Coinstar, Inc.’s expectations as of the date of this release. Coinstar, Inc. undertakes no obligation to update the information provided herein.

###

(Financial Statements Follow)

Contacts:

Media:

Marci Maule

Director of Public Relations

425-943-8277

marci.maule@coinstar.com

Financial Analysts and Investors:

Rosemary Moothart

Director of Investor Relations

425-943-8140

rosemary.moothart@coinstar.com

Appendix A

Use of Non-GAAP Financial Measures

Non-GAAP measures may be provided as a complement to results provided in accordance with United States generally accepted accounting principles (“GAAP”). Non-GAAP measures are not a substitute for measures computed in accordance with GAAP. The definitions of such non-GAAP measures are provided below to allow the reader to reconcile non-GAAP data to that presented in accordance with GAAP. Our non-GAAP measures may be different from the presentation of financial information by other companies.

Adjusted EBITDA from continuing operations is defined as earnings before net interest expense, income taxes, depreciation, amortization and certain other non-cash charges, including the write-off from early retirement of debt and share-based expenses from continuing operations. We believe adjusted EBITDA from continuing operations is an important non-GAAP measure as it provides additional information to users of the financial statements regarding our ability to service, incur or pay down indebtedness. In addition, management uses this non-GAAP measure internally to evaluate performance and manage operations. See below for reconciliation of the most comparable GAAP measure, income from continuing operations, to adjusted EBITDA from continuing operations.

Free cash flow from continuing operations is defined as net cash provided by operating activities from continuing operations after cash paid for capital expenditures for continuing operations. We believe free cash flow is an important non-GAAP measure as it provides additional information to users of the financial statements regarding our ability to service, incur or pay down indebtedness and repurchase our common stock. See below for reconciliation of the most comparable GAAP measure, net cash flows from operating activities from continuing operations, to free cash flow from continuing operations.

Coinstar, Inc.

Consolidated Statements of Net Income

(in thousands, except per share data)

(unaudited)

Coinstar, Inc.

Consolidated Balance Sheets

(in thousands, except share data)

(unaudited)

Coinstar, Inc.

Consolidated Statements of Cash Flows

(in thousands)

(unaudited)

Coinstar, Inc.

Business Segment Information

(in thousands)

(unaudited)

During the first quarter of 2011, we added a segment, New Ventures, to our existing segments redbox, formerly named DVD Services, and Coin, formerly named Coin Services, to reflect changes in how our chief executive officer manages our businesses and allocates resources for the future growth of the company.

As a complement to our Consolidated Statements of Net Income, we are providing the following information related to our business segments, which includes segment operating income (loss), a non-GAAP financial measure. Management, including our chief executive officer, evaluates the performances of our business segments primarily on segment revenue and segment operating income from continuing operations before depreciation, amortization and other, and share-based payments (“segment operating income”). We utilize segment revenue and segment operating income because we believe they provide useful information for effectively allocating resources among business segments, evaluating the health of our business segments based on metrics that management can actively influence, and gauging our investments and our ability to service, incur or pay down debt.