Exhibit 99.2

COINSTAR, INC. ANNOUNCES ADDITIONAL $250 MILLION

STOCK REPURCHASE AUTHORIZATION

BELLEVUE, Wash.—July 21, 2011—Coinstar, Inc. (NASDAQ: CSTR) today announced that the company’s board of directors has authorized the repurchase of an additional $250 million, plus the amount of cash proceeds received by the company from the exercise of stock options by its officers, directors and employees, of Coinstar’s common stock under an additional share repurchase program.

With this authorization and the $12.5 million remaining under the already existing stock repurchase authorization, the company’s total current share repurchase authorization is $262.5 million. Between January 2010 and the end of the second quarter of 2011, Coinstar repurchased approximately 2.4 million shares of its common stock for approximately $112.6 million.

“Coinstar has a proven record of returning capital to our shareholders through stock repurchases,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “Today’s increased authorization demonstrates Coinstar’s solid financial position and our confidence in our future growth prospects.”

The repurchase program authorizes the company to purchase its common stock from time to time through open market purchases, negotiated transactions or other means, including accelerated share repurchases and 10b5-1 trading plans in accordance with applicable securities laws and other restrictions. The additional share repurchase program will continue until the amount of Coinstar common stock authorized is repurchased, the board of directors determines to discontinue or otherwise modify the additional share repurchase program, or the new credit facility agreement separately announced today is terminated.

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 potential stock repurchases. Forward-looking statements are not guarantees of future actions and may vary materially from those 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 ability to obtain future financings, certain negative covenants and restrictions contained in the new credit facility, changes in strategic and financial objectives, 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.

###

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