Exhibit 3.1

RESTATED CERTIFICATE OF INCORPORATION

OF

COINSTAR, INC.

The undersigned does hereby certify on behalf of Coinstar, Inc. (the “Corporation”), a corporation organized and existing under the Delaware General Corporation Law, as follows:

ONE: The undersigned is the duly elected and acting Chief Executive Officer of the Corporation.

TWO: The present name of this corporation is COINSTAR, INC., which is the name under which the Corporation was originally incorporated; and the date of filing of the original Certificate of Incorporation of the Corporation with the Secretary of State of Delaware is October 12, 1993.

THREE: The Amended and Restated Certificate of Incorporation of this Corporation is hereby restated to read as follows:

I.

The name of this Corporation is Coinstar, Inc.

II.

The address of the registered office of the Corporation in the State of Delaware is 1209 Orange Street, City of Wilmington, County of New Castle, and the name of the registered agent of the Corporation in the State of Delaware at such address is The Corporation Trust Company.

III.

The purpose of this Corporation is to engage in any lawful act or activity for which a corporation may be organized under the General Corporation Law of the State of Delaware.

IV.

A. This Corporation is authorized to issue two classes of stock to be designated, respectively, “Common Stock” and “Preferred Stock.” The total number of shares which the Corporation is authorized to issue is sixty-five million (65,000,000) shares. Sixty million (60,000,000) shares shall be Common Stock, each having a par value of one-tenth of one cent ($.001). Five million (5,000,000) shares shall be Preferred Stock, each having a par value of one-tenth of one cent ($.001).

B. The Preferred Stock may be issued from time to time in one or more series. The Board of Directors is hereby authorized, by filing a certificate (a “Preferred Stock Designation”) pursuant to the Delaware General Corporation Law, to fix or alter from time to time the designation, powers, preferences and rights of the shares of each such series and the qualifications, limitations or restrictions of any wholly unissued series of Preferred Stock, and to

1

establish from time to time the number of shares constituting any such series or any of them; and to increase or decrease the number of shares of any series subsequent to the issuance of shares of that series, but not below the number of shares of such series then outstanding. In case the number of shares of any series shall be decreased in accordance with the foregoing sentence, the shares constituting such decrease shall resume the status that they had prior to the adoption of the resolution originally fixing the number of shares of such series.

V.

For the management of the business and for the conduct of the affairs of the Corporation, and in further definition, limitation and regulation of the powers of the Corporation, of its directors and of its stockholders or any class thereof, as the case may be, it is further provided that:

A.

1. The management of the business and the conduct of the affairs of the Corporation shall be vested in its Board of Directors. The number of directors which shall constitute the whole Board of Directors shall be fixed exclusively by one or more resolutions adopted by the Board of Directors.

2. Subject to the rights of the holders of any series of Preferred Stock to elect additional directors under specified circumstances, following the closing of the initial public offering pursuant to an effective registration statement under the Securities Act of 1933, as amended (the “1933 Act”), covering the offer and sale of Common Stock to the public (the “Initial Public Offering”), the directors shall be divided into three classes designated as Class I, Class II and Class III, respectively. Directors shall be assigned to each class in accordance with a resolution or resolutions adopted by the Board of Directors. At the first annual meeting of stockholders following the closing of the Initial Public Offering, the term of office of the Class I directors shall expire and Class I directors shall be elected for a full term of three years. At the second annual meeting of stockholders following the Closing of the Initial Public Offering, the term of office of the Class II directors shall expire and Class II directors shall be elected for a full term of three years. At the third annual meeting of stockholders following the Closing of the Initial Public Offering, the term of office of the Class III directors shall expire and Class III directors shall be elected for a full term of three years. At each succeeding annual meeting of stockholders, directors shall be elected for a full term of three years to succeed the directors of the class whose terms expire at such annual meeting.

Notwithstanding the foregoing provisions of this Article, each director shall serve until his successor is duly elected and qualified or until his death, resignation or removal. No decrease in the number of directors constituting the Board of Directors shall shorten the term of any incumbent director.

3. Subject to the rights of the holders of any series of Preferred Stock, no director shall be removed without cause. Subject to any limitations imposed by law, the Board of Directors or any individual director may be removed from office at any time with cause by the affirmative vote of the holders of a majority of the voting power of all the then-outstanding shares of voting stock of the Corporation, entitled to vote at an election of directors (the “Voting Stock”).

2

4. Subject to the rights of the holders of any series of Preferred Stock, any vacancies on the Board of Directors resulting from death, resignation, disqualification, removal or other causes and any newly created directorships resulting from any increase in the number of directors, shall, unless the Board of Directors determines by resolution that any such vacancies or newly created directorships shall be filled by the stockholders, except as otherwise provided by law, be filled only by the affirmative vote of a majority of the directors then in office, even though less than a quorum of the Board of Directors, and not by the stockholders. Any director elected in accordance with the preceding sentence shall hold office for the remainder of the full term of the director for which the vacancy was created or occurred and until such director’s successor shall have been elected and qualified.

B.

1. Subject to paragraph (h) of Section 43 of the Bylaws, the Bylaws may be altered or amended or new Bylaws adopted by the affirmative vote of at least sixty-six and two-thirds percent (66 ²/3%) of the voting power of all of the then-outstanding shares of the Voting Stock. The Board of Directors shall also have the power to adopt, amend, or repeal Bylaws.

2. The directors of the Corporation need not be elected by written ballot unless the Bylaws so provide.

3. No action shall be taken by the stockholders of the Corporation except at an annual or special meeting of stockholders called in accordance with the Bylaws and following the closing of the Initial Public Offering no action shall be taken by the stockholders by written consent.

4. Special meetings of the stockholders of the Corporation may be called, for any purpose or purposes, by (i) the Chairman of the Board of Directors, (ii) the Chief Executive Officer, or (iii) the Board of Directors pursuant to a resolution adopted by a majority of the total number of authorized directors (whether or not there exist any vacancies in previously authorized directorships at the time any such resolution is presented to the Board of Directors for adoption), and shall be held at such place, on such date, and at such time as the Board of Directors shall fix.

5. Advance notice of stockholder nominations for the election of directors and of business to be brought by stockholders before any meeting of the stockholders of the Corporation shall be given in the manner provided in the Bylaws of the Corporation.

VI.

A. A director of the Corporation shall not be personally liable to the Corporation or its stockholders for monetary damages for any breach of fiduciary duty of a director, except for liability (i) for any breach of the director’s duty of loyalty to the Corporation or its stockholders, (ii) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law (iii) under Section 174 of the Delaware General Corporation Law, or (iv) for any transaction from which the director derived an improper personal benefit. If the

3

Delaware General Corporation Law is amended after approval by the stockholders of this Article to authorize corporate action further eliminating or limiting the personal liability of directors, then the liability of a director shall be eliminated or limited to the fullest extent permitted by the Delaware General Corporation Law, as so amended.

B. Any repeal or modification of this Article VI shall be prospective and shall not affect the rights under this Article VI in effect at the time of the alleged occurrence of any act or omission to act giving rise to liability or indemnification.

VII.

A. The Corporation reserves the right to amend, alter, change or repeal any provision contained in this Certificate of Incorporation, in the manner now or hereafter prescribed by statute, except as provided in paragraph B. of this Article VII, and all rights conferred upon the stockholders herein are granted subject to this reservation.

B. Notwithstanding any other provisions of this Certificate of Incorporation or any provision of law which might otherwise permit a lesser vote or no vote, but in addition to any affirmative vote of the holders of any particular class or series of the Voting Stock required by law, this Certificate of Incorporation or any Preferred Stock Designation, the affirmative vote of the holders of at least sixty-six and two-thirds percent (66- ²/3%) of the voting power of all of the then-outstanding shares of the Voting Stock, voting together as a single class, shall be required to alter, amend or repeal Articles V, VI, and VII.

FOUR: This Restated Certificate of Incorporation only restates and integrates and does not further amend the provisions of the Corporation’s Amended and Restated Certificate of Incorporation as heretofore amended and supplemented and there is no discrepancy between those provisions and the provisions of the foregoing Restated Certificate of Incorporation. This Restated Certificate of Incorporation has been duly adopted by the Corporation’s Board of Directors in accordance with the provisions of Section 245 of the General Corporation Law of the State of Delaware.

Dated this 26th day of October, 2010.

4