Exhibit 99.1

CONTACTS:

Media:

Marci Maule

Director of Public Relations

mmaule@coinstar.com

425-943-8277

Investors:

Rosemary Moothart

Director of Investor Relations

rosemary.moothart@coinstar.com

425-943-8140

FOR IMMEDIATE RELEASE

COINSTAR APPOINTS J. SCOTT DI VALERIO CHIEF FINANCIAL OFFICER

BELLEVUE, Wash. – Jan. 20, 2010 – Coinstar, Inc. (NASDAQ: CSTR), today announced the appointment of J. Scott Di Valerio as chief financial officer effective March 2, 2010. Di Valerio joined the company on January 19 and will work with Paul Davis, Coinstar chief executive officer, prior to taking over as CFO.

“Scott brings with him a strong finance, management and business background with high-growth, world-class organizations, as well as a demonstrated ability to communicate effectively with the investment community,” said Paul Davis. “The depth and breadth of his experience further enhances our management team, and we look forward to his contributions as we execute our strategic plans for growth and success as a leader in automated retail.”

Di Valerio, 47, has over 25 years finance, operations and management experience, most recently serving as President of the Americas for the Lenovo Group Limited, a leading computer manufacturer. Previously, he held senior positions at Microsoft Corp., where he served as the company’s corporate vice president of Finance and Administration and chief accounting officer, and as corporate vice president of the Original Equipment Manufacturer (OEM) division. Before joining Microsoft, Di Valerio served as corporate vice president corporate controllership at The Walt Disney Company, chief financial officer of Mindwave Software Inc., and partner at PricewaterhouseCoopers.

Di Valerio is a certified public accountant and holds a bachelor’s degree in business administration from the University of San Diego.

James Blanda, a Tatum, LLC, partner will stay on as interim CFO with the company through March 1 prior to the transition to Di Valerio.

About Coinstar, Inc.

Coinstar, Inc. (NASDAQ: CSTR) is a leading provider of automated retail solutions offering convenient products and 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 products and services include e-payment products – such as gift cards, prepaid debit cards and other prepaid products – and money transfer services. The Company’s products and services can be found at more than 90,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 the foregoing press release are “forward-looking statements” within the meaning of the Private Securities Litigation Reform Act of 1995. Words indicating future events, performance, results and actions, such as “estimate” and “expect,” and 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 press release include statements regarding management transition matters, including Mr. Di Valerio’s employment with the Company. Forward-looking statements are not guarantees of future actions, events or performance, which may vary materially from those expressed or implied in such statements. Differences may result from, among other things, actions taken by the Company or Mr. Di Valerio, including those beyond the Company’s or Mr. Di Valerio’s control. Such risks and uncertainties include, but are not limited to, the failure of Mr. Di Valerio to remain with the Company for the expected period. The foregoing list of risks and uncertainties is illustrative, but by no means exhaustive. For more information on factors that may affect future performance, results or actions, please review “Risk Factors” described in our most recent Quarterly Report on Form 10-Q filed with the Securities and Exchange Commission (the “SEC”), as well as other filings with the SEC. These forward-looking statements reflect the Company’s expectations as of the date hereof. The Company undertakes no obligation to update the information provided herein.