Exhibit 99.1

COINSTAR, INC. ANNOUNCES 2011 SECOND QUARTER RESULTS

Company’s Core Businesses Generate Significant Earnings Growth

BELLEVUE, Wash.—July 28, 2011—Coinstar, Inc. (NASDAQ: CSTR) today announced financial results for the second quarter and six months ended June 30, 2011.

“We had a very solid quarter delivering strong top and bottom line results,” said Paul Davis, chief executive officer of Coinstar, Inc. “We are pleased to have won the Safeway Coin business and are excited about the continued market share gains we’re enjoying with redbox. The video game rollout has started nicely as we’ve been able to broaden our demographic reach and provide consumers access to games at affordable prices.”

Financial highlights for the 2011 second quarter and six months ended June 30, 2011, included:

“Our focus on improving operations and investing in the business contributed to our strong earnings growth in the second quarter,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “Our solid financial position enables us to prudently invest in our business and opportunistically return capital to our shareholders. We will continue to focus on enhancements to our processes that will help us to drive additional growth and profitability.”

Revenue for the second quarter of 2011 increased 27.1% to $435.2 million compared with the second quarter of 2010, driven primarily by redbox revenue growth of 33.8% to $363.9 million reflecting new kiosk installations and growth in same store sales. Coin revenue grew 1.0% to $71.1 million reflecting an increase in the average transaction size.

Operating income for the second quarter of 2011 was $58.2 million, which resulted in an operating margin of 13.4%, compared with operating income of $29.3 million and an operating margin of 8.6% in the second quarter of 2010. The increase in operating margin percentage primarily reflects increasing leverage in expenses related to the redbox segment and that 2010 included a pre-tax charge of approximately $2.0 million related to the company’s decision to exit the DVDXpress branded business.

Income from continuing operations for the second quarter of 2011 was $31.5 million, or diluted earnings per share from continuing operations of $0.98, compared with $12.8 million, or $0.39 per share, in the second quarter of 2010.

Net income for the second quarter of 2011, which includes both continuing and discontinued operations, was $26.7 million, or diluted earnings per share of $0.83, compared with $13.4 million, or $0.41 per share, in the second quarter of 2010.

For the first six months of 2011 revenue was $859.3 million, an increase of 29.1% compared with the first six months of 2010. Operating income for the first six months of 2011 was $89.6 million, which resulted in an operating margin of 10.4%, compared with operating income of $53.9 million and an operating margin of 8.1% in the first six months of 2010. Net income for the first six months of 2011 was $35.2 million, or diluted earnings per share of $1.10, compared with net income of $19.8 million, or $0.62 per share, in the first six months of 2010.

Net cash flows from operating activities from continuing operations in the second quarter of 2011 was $111.9 million, compared with $104.2 million in the second quarter of 2010. Cash paid for capital expenditures for continuing operations for the second quarter of 2011 was $49.4 million, compared with $52.8 million in the second quarter of 2010, with the decrease reflecting fewer planned redbox kiosk installations offset in part by continued investment in infrastructure. Free cash flow from continuing operations for the second quarter of 2011 was $62.5 million, compared with $51.4 million in the second quarter of 2010.

During the second quarter, Coinstar settled the $50 million accelerated share repurchase (ASR) program announced in February 2011. As of the end of the second quarter, the company had a remaining total authorization to repurchase $12.5 million of Coinstar’s common stock.

On July 21, 2011, Coinstar announced that the company’s board of directors had 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 at the end of the second quarter, Coinstar’s total current share repurchase authorization is $262.5 million.

Also, on July 21, 2011, Coinstar announced a new senior credit facility 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.

Guidance

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

For the 2011 third 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 second 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 August 11, 2011, at 1-888-286-8010 or 1-617-801-6888, passcode 71692556.

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 33,300 DVD kiosks and 18,900 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). 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.

Segment operating income reconciled to GAAP operating income