Exhibit 99.1

COINSTAR, INC. ANNOUNCES REVISED 2009 FOURTH QUARTER AND FULL YEAR RESULTS

REFLECTING LEGAL SETTLEMENT INVOLVING E-PAYMENT BUSINESS

Settlement Decreases 2009 Fourth Quarter and Full Year EPS by $0.07;

Management Reaffirms 2010 First Quarter and Full Year Guidance

BELLEVUE, Wash.—February 23, 2010—Coinstar, Inc. (NASDAQ: CSTR) today announced that the company revised financial results for the fourth quarter and full year ended December 31, 2009, due to a legal settlement involving its E-Payment services business. The revised results are reflected in the Annual Report on Form 10-K to be filed by the company today.

On February 19, 2010, Coinstar settled an action filed by Apparel Sales, Inc. (“ASI”) in 2005 against one of the subsidiaries of its E-Payment services business for $4.0 million and ASI has agreed to dismiss its complaint with prejudice. The company had previously accrued for $0.5 million of the $4.0 million settlement expense and as a result, $3.5 million of expense, or approximately ($0.07) per diluted share, is included in the “Proxy, write-off of acquisition costs, and litigation settlement” line item in the Consolidated Statement of Operations for the fourth quarter and full year ended December 31, 2009.

The impact of the settlement is included in the revised financial highlights below.

For the quarter ended December 31, 2009:

For the full year ended December 31, 2009:

Revenue for the fourth quarter of 2009 was $328.0 million, an increase of 43.9 percent compared with revenue of $227.9 million in the fourth quarter of 2008. The increase is primarily due to the growth in DVD revenue, which was $231.8 million in the fourth quarter of 2009, an increase of 73.2 percent compared with $133.8 million in the fourth quarter of 2008.

Income from operations for the fourth quarter was $16.5 million, which includes a pre-tax, non-cash charge of approximately $7.4 million related to goodwill impairment in Coinstar’s Money Transfer services business and $3.5 million of expense recognized in the quarter for the ASI settlement. This resulted in an operating margin of 5.0 percent, compared with income from operations of $21.4 million and an operating margin of 9.4 percent in the fourth quarter of 2008. Operating margin also decreased as a result of higher DVD product costs.

Income from continuing operations for the fourth quarter was $3.4 million, including approximately $4.5 million, net of tax, related to the non-cash goodwill impairment charge and $2.1 million of expense, net of tax, related to the ASI settlement, compared with $9.9 million in the fourth quarter of 2008.

Net income attributable to Coinstar, Inc. for the fourth quarter was $3.4 million, or $0.11 per diluted share, including approximately ($0.14) per diluted share related to the non-cash goodwill impairment charge and approximately ($0.07) per diluted share related to the ASI settlement, compared with $4.2 million, or $0.15 per diluted share, in the fourth quarter of 2008.

Revenue for 2009 was $1.1 billion, an increase of 50.3 percent compared with revenue of $761.7 million in 2008. The increase reflects the growth in DVD revenue, which was $773.5 million in 2009, an increase of 99.1 percent compared with $388.5 million in 2008. The growth in DVD revenue for the fourth quarter and the full year was driven by the 8,700 DVD kiosks installed during the year, as well as revenue growth at existing machines.

Income from operations for 2009 was $84.3 million, including approximately $7.4 million related to the pre-tax non-cash charge related to goodwill impairment in Coinstar’s Money Transfer services business and $3.5 million of expense recognized for the ASI settlement. This resulted in an operating margin of 7.4 percent, compared with income from operations of $76.4 million and an operating margin of 10.0 percent in 2008. Operating margin for the year also decreased as a result of higher DVD product costs.

Income from continuing operations for the year was $29.3 million, including approximately $4.5 million, net of tax, related to the non-cash goodwill impairment charge and $2.1 million of expense, net of tax, related to the ASI settlement, compared with $33.5 million in 2008.

Net income attributable to Coinstar, Inc. for the year was $53.7 million, or $1.76 per diluted share, including approximately ($0.15) per diluted share related to the non-cash goodwill impairment charge and approximately ($0.07) per diluted share related to the ASI settlement, compared with $14.1 million, or $0.50 per diluted share, in 2008. Both 2009 and 2008 include the impact from discontinued operations from the sale of our Entertainment business of $28.0 million, or $0.92 per diluted share, in 2009 and a loss of ($5.0) million, or ($0.17) per diluted share, in 2008.

Other Information

Cash paid for capital expenditures for the fourth quarter ended December 31, 2009 was $48.3 million, compared with $35.0 million in the fourth quarter of 2008, with the increase primarily due to our investment in DVD kiosks during the fourth quarter of 2009.

2010 Full Year and First Quarter Guidance

Coinstar management reaffirmed guidance for the full year 2010 that was previously provided on February 11, 2010, and guidance for the first quarter of 2010 that was previously provided on February 16, 2010.

For 2010, management expects revenue in the range of $1.465 billion to $1.565 billion, EBITDA in the range of $250 million to $265 million and GAAP EPS attributable to Coinstar, Inc. in the range of $1.50 to $1.65 on a

fully diluted basis. For the first quarter of 2010, management expects revenue in the range of $315 million to $335 million, EBITDA in the range of $43 million to $48 million and GAAP EPS attributable to Coinstar, Inc. in the range of $0.08 to $0.14 on a fully diluted basis.

This guidance includes the impact on revenue and costs related to challenges in securing DVD content, as well as the number and timing of planned kiosk installations.

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 its retailers. The company’s core automated retail businesses are self-service coin counting and self-service DVD rental. Other Coinstar services include e-payment and money transfer services. The company’s services can be found at more than 95,000 points of presence including supermarkets, drug stores, mass merchants, financial institutions, convenience stores, restaurants, and money transfer agents. 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,” 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, payment of increased service fees to retailers, 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 filed with the Securities and Exchange Commission on February 23, 2010. 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

Investors:

Rosemary Moothart

Director of Investor Relations

425-943-8140

rosemary.moothart@coinstar.com

Appendix A

(in thousands)

Non-GAAP 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 definition of adjusted EBITDA from continuing operations, a non-GAAP measure, is provided below to allow the reader to reconcile non-GAAP data to that presented in accordance with GAAP. Our non-GAAP measure may be different from the presentation of financial information by other companies.

Adjusted EBITDA from continuing operations, as defined, represents earnings before net interest expense, income taxes, depreciation, amortization and certain other non-cash charges including the write-off from early retirement of debt, goodwill impairment, and stock-based compensation and share-based expenses from continuing operations. We believe adjusted EBITDA from continuing operations is an important non-GAAP measure as it provides useful information to investors 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.

Coinstar, Inc.

Consolidated Statements of Operations

(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)