Exhibit 99.1

Coinstar, Inc. Announces Gregg Kaplan’s Planned Departure in March 2013

Appoints Seasoned Leader Anne Saunders President of Redbox

BELLEVUE, Wash.— August 13, 2012—Coinstar, Inc. (Nasdaq: CSTR), today announced that Gregg Kaplan, president and chief operating officer of Coinstar, Inc. and founder and interim president of Redbox Automated Retail, LLC, Coinstar’s wholly-owned subsidiary, will be leaving the company in order to pursue new opportunities. Kaplan will remain president and chief operating officer of Coinstar through March 31, 2013, and will continue to oversee Coinstar’s new ventures and new business development while focusing on transitioning with the new Redbox president.

Coinstar also announced today that Anne Saunders, most recently executive vice president and chief marketing officer at Knowledge Universe where she was responsible for business strategy and marketing functions, has been appointed president of Redbox, effective August 27, 2012. Saunders brings to Redbox extensive executive experience across a variety of industries, including past senior leadership roles at Bank of America, Starbucks and AT&T. As president of Redbox, Saunders will lead the entire Redbox organization, reporting to Coinstar’s Chief Executive Officer Paul Davis.

“On behalf of Coinstar’s Board of Directors and the entire organization, I want to thank Gregg for his countless contributions to the company over the last decade,” said Davis. “Gregg has been instrumental in not only the success of Redbox but also in all facets of our business. His decision to leave the company next year was made with much thought and consideration, and we fully appreciate and respect his desire to embark on his next venture. We appreciate that Gregg will remain with us for the transition, and we look forward to continuing to benefit from his wisdom and energy. Gregg is a true entrepreneur and has left an indelible imprint on everyone here, and we wish him only the best in the future.”

Kaplan said, “For more than a decade, I have had the privilege of developing and leading Redbox, a leader in today’s home entertainment industry. We started Redbox in 2002 with only a few kiosks, and working tirelessly with the Redbox team – which I sincerely believe is the best in the business – we have transformed this industry and now boast more than 38,500 kiosks around the United States and Canada. As part of the Coinstar family, I have also had the opportunity to enhance operations and R&D and help the company become a leader in automated retail. To say that I am extremely proud of everything we have accomplished here is an understatement. I look forward to continuing to work closely with the teams, including our talented and dedicated employees around the country, to ensure a smooth transition in the months ahead.”

“We are thrilled to welcome Anne Saunders to our leadership team and we are confident that she is the ideal candidate to lead Redbox through its next chapter,” added Davis. “Anne is a true innovator and brand builder with extensive experience in developing and growing new revenue streams, business optimization and consumer marketing. Anne has had a positive impact everywhere she has worked, and on behalf of the entire Board and management team, I welcome Anne to the Coinstar family.”

Kaplan continued, “I know first-hand the qualities it takes to lead Redbox and I have the utmost confidence that Anne has the right background and experience to lead the organization. We will benefit from Anne’s leadership and consumer brand experience, and I look forward to working closely with her over the coming months to assist in transitioning Anne into her new role.”

Anne Saunders

Anne Saunders, 51, is a successful brand builder and people leader with a breadth of experience across general management, marketing and operations roles in start-up and Fortune 100 companies; B2B and

B2C businesses; and the retail, technology, telecommunications and financial services industries. Most recently, Saunders served as executive vice president and chief marketing officer of Knowledge Universe, where she was responsible for creating the company’s business strategy, accelerating revenue growth, and developing new revenue streams. From 2007 to 2009, Saunders worked at Bank of America, first as senior vice president, brand executive, then as senior vice president, consumer bank executive. Prior to that, Saunders held a number of roles at Starbucks where she was responsible for global brand strategy, marketing and communications, as well as launching and growing the Starbucks Card to a $1 billion revenue business. Saunders holds a B.A. in economics from Northwestern University and an M.B.A. from Fordham University.

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 38,500 DVD kiosks and 20,200 coin-counting kiosks in supermarkets, drug stores, mass merchants, financial institutions, convenience stores, and restaurants. Redbox also offers DVD rentals through additional kiosks acquired from NCR Corporation in June 2012. For more information, visit www.coinstarinc.com.

About Redbox

Redbox Automated Retail, LLC, a wholly-owned subsidiary of Coinstar, Inc. (Nasdaq: CSTR), offers new-release DVD, Blu-ray Disc™ and video-game rentals through its network of conveniently located, self-service kiosks. Redbox has rented more than 2 billion discs and is available at approximately 38,500 kiosks across over 31,000 locations nationwide, including select McDonald’s restaurants, leading grocery, drug and convenience stores, select Walmart locations and Walgreens locations in select markets. Redbox also offers DVD rentals through additional kiosks acquired from NCR Corporation in June 2012. For more information, visit www.redbox.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,” “will,” “expect,” “intend,” “anticipate,” and variations of such words, and similar expressions identify forward-looking statements, but their absence does not mean that a statement is not forward-looking. The forward-looking statements in this release include statements regarding Coinstar’s and Redbox’s management changes. Forward-looking statements are not guarantees of future actions or events, which may vary materially from those expressed or implied in such statements. Differences may result from actions taken by Coinstar or Redbox, as well as from risks and uncertainties beyond Coinstar’s and Redbox’s control. Such risks and uncertainties include, but are not limited to, timing and integration of management changes, changes in strategic and financial objectives, and the ability to attract new retailers, penetrate new markets and distribution channels and react to changing consumer demands. The foregoing list of risks and uncertainties is illustrative, but by no means exhaustive. For more information on factors that may affect Coinstar and Redbox, please review “Risk Factors” and other disclosures described in Coinstar’s most recent Annual Report on Form 10-K and subsequent Quarterly Reports on Form 10-Q filed with the Securities and Exchange Commission, as well as other public filings with the Securities and Exchange Commission. These forward-looking statements reflect Coinstar’s and Redbox’s expectations as of the date of this release. Coinstar undertakes no obligation to update the information provided herein.

###

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