UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

WASHINGTON, D.C. 20549

FORM 8-K

CURRENT REPORT

Pursuant to Section 13 or 15(d) of the

Securities Exchange Act of 1934

Date of Report (Date of earliest event reported) April 22, 2010

COINSTAR, INC.

(Exact name of registrant as specified in its charter)

1800 – 114^th Avenue SE

BELLEVUE, WA 98004

(Address of Principal Executive Offices and Zip Code)

Registrant’s telephone number, including area code: (425) 943-8000

Check the appropriate box below if the Form 8-K filing is intended to simultaneously satisfy the filing obligation of the registrant under any of the following provisions:

On April 22, 2010, Redbox Automated Retail, LLC (“Redbox”), a wholly-owned subsidiary of Coinstar, Inc. (“Coinstar”), entered into a disc output lease and rental agreement (the “Agreement”) with Twentieth Century Fox Home Entertainment LLC (“Fox”). Redbox estimates that it would pay Fox approximately $394.5 million, during the term of the Agreement, which is expected to last from April 22, 2010, through April 21, 2015. However, at Fox’s discretion, the Agreement may expire earlier on April 21, 2013.

Under the Agreement, Redbox agrees to license minimum quantities of theatrical and direct-to-video DVDs for rental at each of the more than 20,200 locations that have a DVD-rental kiosk owned and/or operated by Redbox in the United States. Under the Agreement, Redbox will make the DVDs available for rental 28 days after the “retail street date,” the earliest date established by Fox on which the DVDs are initially made available to the general public, whether on a rental or sell-through basis. In addition, and pursuant to the terms of the Agreement, Redbox will move to voluntarily dismiss its lawsuit against Fox relating to Redbox’s access to Fox titles.

Certain statements in the foregoing paragraphs are “forward-looking statements” within the meaning of the Private Securities Litigation Reform Act of 1995. Words 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 release include statements regarding Redbox’s relationship with Fox relating to, among other things, a disc output lease and rental arrangement. 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, Redbox or Fox, including those beyond our or Redbox’s control. Such risks and uncertainties include, but are not limited to, the 28 day rental window, the early termination or the renegotiation on materially adverse terms of the Agreement, and failure to abide by the terms and requirements of the Agreement. The foregoing list of risks and uncertainties is illustrative, but by no means exhaustive. For more information on factors that may affect future performance, including our relationship with Fox, please review “Risk Factors” described in our most recent Form 10-K and any subsequent Quarterly Reports on Form 10-Q filed with the Securities and Exchange Commission, as well as other filings. These forward-looking statements reflect Coinstar’s expectations as of the date hereof. Coinstar undertakes no obligation to update the information provided herein.

2

SIGNATURE

Pursuant to the requirements of the Securities Exchange Act of 1934, the registrant has duly caused this report to be signed on its behalf by the undersigned hereunto duly authorized.

3