Exhibit 99.1

COINSTAR, INC. ANNOUNCES 2010 FOURTH QUARTER AND FULL YEAR RESULTS

Company Drives 55% Year Over Year Earnings Growth in 2010

BELLEVUE, Wash.—Feb. 3, 2011—Coinstar, Inc. (NASDAQ: CSTR) today announced financial results for the fourth quarter and full year ended December 31, 2010.

“We grew our fourth quarter revenue 31% over the prior year, and while this was not in line with our expectations, we still delivered $2.03 in earnings per share for the full year,” said Paul Davis, chief executive officer of Coinstar, Inc. “We have taken definitive steps to correct the issues we encountered with our redbox business in the fourth quarter and will be tracking progress closely. Our coin business remains solid with same store sales growth of approximately 10% and redbox increased its unit market share to 29.8%. We remain optimistic about our core businesses as well as future opportunities with new automated retail concepts and we are committed to driving continued profitable growth.”

Financial highlights for the 2010 fourth quarter and full year included:

“Overall, this was a tremendous year for Coinstar exhibited by our revenue, adjusted EBITDA and EPS growth,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “Nonetheless, we did not finish the year as strongly as we expected. We do expect continued growth as we focus on providing a compelling offering to our consumers that is a significant benefit to our retail partners and increases our shareholder value.”

Revenue for the fourth quarter of 2010 increased 31% to $390.8 million compared with the fourth quarter of 2009, driven primarily by growth in DVD revenue, which increased 38% to $319.6 million, and by Coin revenue which grew 7% to $71.2 million.

Income from operations for the fourth quarter of 2010 was $43.2 million, resulting in an operating margin of 11%, including $3.1 million in share-based payments expense related to the company’s agreements with Sony Pictures Home Entertainment (Sony) and Paramount Home Entertainment Inc. This compares with income from operations of $29.7 million and an operating margin of 10% in the fourth quarter of 2009, which included $0.3 million in share-based payments expense related to the Sony agreement.

Income from continuing operations for the fourth quarter of 2010 was $22.4 million, with diluted earnings per share of $0.68, compared with $11.6 million, and $0.37, in the fourth quarter of 2009.

Coinstar recorded a loss from discontinued operations of $10.7 million, net of tax, or a loss of $0.33 per share, in the fourth quarter.

Net income attributable to Coinstar, Inc. for the fourth quarter of 2010, which includes both continuing and discontinued operations, was $11.7 million, with diluted earnings per share of $0.35. This compares with $3.4 million, and $0.11, in the fourth quarter of 2009.

Revenue for 2010 was $1,436.4 million, an increase of 39% compared with 2009. Income from operations for 2010 was $143.2 million compared with income from operations of $104.7 million in 2009.

Income from continuing operations for 2010 was $65.9 million, with diluted earnings per share of $2.03, compared with $43.7 million, and $1.31, in 2009.

Net income attributable to Coinstar, Inc. for 2010 was $51.0 million, with $1.57 per diluted share, including a loss, net of tax, of $14.9 million from discontinued operations. This compares with net income attributable to Coinstar, Inc. of $53.6 million, and $1.76, in 2009, which included income from discontinued operations, net of tax, of $13.6 million offset by a net loss of $3.6 million attributable to non-controlling interests.

Cash paid for capital expenditures for continuing operations for the fourth quarter of 2010 was $38.4 million, compared with $46.5 million in the fourth quarter of 2009. Free cash flow from continuing operations for the fourth quarter of 2010 was $48.6 million, compared with $8.4 million in the fourth quarter of 2009.

Coinstar announced that the company’s board of directors authorized the repurchase of an additional $50 million of Coinstar’s common stock. The company currently has a total authorization to repurchase $74.5 million of Coinstar’s common stock.

Guidance

For the 2011 full year, Coinstar management expects:

For the 2011 first 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 fourth 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.coinstar.com. A recording of the call will be available approximately two hours after the call ends through February 17, 2011, at 1-888-286-8010 or 1-617-801-6888, passcode 42299302.

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 30,200 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.coinstar.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,” “will,” 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 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 termination, non-renewal or renegotiation on materially adverse terms of our contracts with our significant retailers, payment of increased service fees to retailers, 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, actions relating to legal, regulatory, and similar proceedings 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 Reports 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 provided by 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)

At December 31, 2010, we reflected both the E-payment and Money Transfer businesses as discontinued operations for all periods presented. As a result, our business segments are now DVD services and Coin services. The operating costs related to continuing corporate activities have been reallocated to these two segments.

As a complement to our Consolidated Statements of Net Income, we are providing the following information related to our business segments: