Exhibit 99.1

COINSTAR, INC. ANNOUNCES NEW FIVE-YEAR SENIOR CREDIT FACILITY

BELLEVUE, Wash.—July 21, 2011—Coinstar, Inc. (NASDAQ: CSTR) today announced that it has entered into a new credit facility agreement consisting of a senior secured $450 million revolving line of credit commitment that, under certain conditions, may be increased up to an additional $250 million in aggregate and a senior secured $175 million five-year amortizing term loan facility.

The new agreement, which closed on July 15, 2011, amends and restates in its entirety the credit agreement originally entered into by Coinstar on November 20, 2007, and all previous amendments and restatements. The new agreement provides Coinstar with greater flexibility than the prior agreement in certain matters, including the incurrence of indebtedness, capital expenditures, restricted payments, and permitted acquisitions. The interest rates and revolving line commitment fees are lower than those under the prior credit facility.

“We are very pleased to have negotiated financing to support the business that carries lower spreads and fees and fewer restrictions than our previous credit facility, giving us greater opportunities to create value for our shareholders,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “The expanded credit facility will increase Coinstar’s financial flexibility and will be integral to the company’s long-term growth and success.”

A portion of the immediate term loan proceeds will be used to repay the amount outstanding under Coinstar’s prior revolving line of credit, which was $150 million as of March 31, 2011. The remainder of the term loan proceeds will be available for other working capital needs. The revolving line of credit under the new agreement is currently undrawn. The term loan and revolving line of credit will mature on July 15, 2016.

Bank of America, N.A. acted as administrative agent; Merrill Lynch, Pierce, Fenner & Smith Incorporated and Wells Fargo Securities, LLC, acted as joint lead arrangers and joint book managers; and Wells Fargo Bank, National Association acted as syndication agent. HSBC, U.S. Bank National Association and RBC Capital Markets acted as co-documentation agents.

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 future use of its new credit facility. Forward-looking statements are not guarantees of future actions and they 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, the ability to generate sufficient cash flow to service the indebtedness and 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