Exhibit 99.1

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

Company Drives 33.2% Revenue Growth and $1.00 EPS in Fourth Quarter;

Expects Revenue to Top $2.2 Billion in 2012

2012 Initiatives Include Joint Venture with Verizon to Offer New Video Entertainment Choice

Company Announces Agreement to Acquire NCR’s DVD Business Assets

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

“Our strong finish in the fourth quarter capped a great year for Coinstar, including revenue over $1.8 billion, diluted EPS of $3.61 per share and free cash flow over $227 million,” said Paul Davis, chief executive officer of Coinstar, Inc. “The strength of our core businesses provides a solid foundation that enables us to focus on key growth initiatives in 2012, including our joint venture with Verizon that was announced earlier today. We are delighted to be partnering with Verizon to offer consumers affordable entertainment in both physical and streaming formats and look forward to launching our service in the second half of the year.”

Davis continued, “We also are very pleased to announce the acquisition of the assets of NCR’s DVD business and the opportunity to work with NCR as we develop our portfolio of innovative, self-service concepts.”

The acquisition is subject to Hart-Scott-Rodino Antitrust Improvement Act (HSR) review. Assuming HSR approval, the company expects the transaction to close no later than the third quarter of 2012.

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

“Our results underscore our ability to grow our core businesses profitably and generate substantial free cash flow at the same time,” said J. Scott Di Valerio, chief financial officer of Coinstar, Inc. “We are very pleased with the operational performance throughout the organization in 2011 and will continue to focus on the processes that drive success. Moving forward we are confident in our ability to execute enabling us to generate positive cash flows even as we fund our organic growth and strategic initiatives.”

Revenue for the fourth quarter of 2011 increased 33.2% to $520.5 million compared with the fourth quarter of 2010, driven primarily by Redbox revenue growth of 39.5% to $445.6 million primarily reflecting new kiosk installations, strong performance of new release titles, and consumer acceptance of the price increase implemented October 31, 2011. Coin revenue grew 4.8% to $74.4 million, reflecting growth in same store sales.

Operating income for the fourth quarter of 2011 was $54.7 million, which resulted in an operating margin of 10.5%, compared with operating income of $43.2 million and an operating margin of 11.0% in the fourth quarter of 2010.

Income from continuing operations for the fourth quarter of 2011 was $31.5 million, or diluted earnings per share from continuing operations of $1.00, an increase in diluted earnings per share of 47.1% compared with $22.4 million, or $0.68 per share, in the fourth quarter of 2010.

For the 2011 full year revenue was $1,845.4 million, an increase of 28.5% compared with 2010. Operating income for 2011 was $209.9 million, which resulted in an operating margin of 11.4%, compared with operating income of $143.2 million and an operating margin of 10.0% in 2010. Income from continuing operations for 2011 was $115.0 million, or diluted earnings per share of $3.61, an increase in diluted earnings per share of 77.8% compared with income from continuing operations of $65.9 million, or $2.03 per share, in 2010.

Net cash flows from operating activities from continuing operations in the fourth quarter of 2011 was $144.9 million, compared with $87.0 million in the fourth quarter of 2010. Cash paid for capital expenditures for continuing operations for the fourth quarter of 2011 was $44.5 million, compared with $38.4 million in the fourth quarter of 2010. Free cash flow from continuing operations for the fourth quarter of 2011 was $100.4 million, compared with $48.6 million in the fourth quarter of 2010.

Guidance

Coinstar’s guidance includes financial measures related to core and non-core activities. The core financial measures are non-GAAP financial measures as they exclude certain items related to non-core activities. Definitions of these terms are provided in Appendix A.

For the 2012 full year, Coinstar management expects:

For the 2012 first quarter, Coinstar management expects:

Additional Information

Coinstar has provided additional comments on guidance in prepared remarks that also review the company’s 2011 operating and financial results and 2012 initiatives. The prepared remarks are posted on the Investor Relations section of the corporate website at www.coinstarinc.com along with this press release and the fourth quarter Investor Update.

Conference Call

Paul Davis and J. Scott Di Valerio will host a conference call today at 2:00 p.m. PST (5:00 p.m. EST) to answer questions related to the company’s business performance, financial results, guidance, and recent announcements. The conference call will be webcast live and archived on the Investor Relations

section of Coinstar’s website. A recording of the call will be available through February 20, 2012, at 888-286-8010 or 617-801-6888, passcode 94593099.

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 and video game rental and Coinstar^® self-service coin-counting brands. The company has approximately 35,400 DVD kiosks and 20,200 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., Redbox, Verizon, or NCR, as well as from risks and uncertainties beyond Coinstar, Inc.’s control. Such risks and uncertainties include, but are not limited to, competition from other digital entertainment providers, the ability to achieve the strategic and financial objectives for our entry into a new business, our limited ability to direct the management or policies of the new joint venture, the ability to gain government approval for the NCR asset acquisition or acquire all of the desired assets in such transaction, failure to receive the expected benefits of the NCR relationship, 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, suppliers and other third-party providers, 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 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. The table below provides a 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. The table below provides a reconciliation of the most comparable GAAP measure, net cash flows from operating activities from continuing operations, to free cash flow from continuing operations.

Use of Core Non-GAAP Financial Measures in 2012 Guidance

We believe investors should consider our core results because they are more indicative of our ongoing performance and trends and are more consistent with how management evaluates our operational results and trends.

Core 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, as well as before non-core adjustments, which are net of applicable taxes and primarily include acquisition expenses, such as advisor fees and closing costs, and non-recurring gain/loss related to the formation of our joint venture with Verizon, as well as gains/(losses) from equity investments, which represent our share of income from entities we do not consolidate or control.

Core EPS is defined as earnings per share from continuing operations excluding non-core adjustments, which are net of applicable taxes and primarily include acquisition expenses and non-recurring gains/losses related to the formation of our joint venture with Verizon, as well as gain/(loss) from equity investments.

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 certain 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