Exhibit 3.1

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

COLLECTIVE BRANDS, INC.

ARTICLE ONE

The name of the corporation is Collective Brands, Inc.

ARTICLE TWO

The address of the corporation’s registered office in the State of Delaware is Corporation Trust Center, 1209 Orange Street, in the City of Wilmington, County of New Castle, Delaware 19801. The name of its registered agent at such address is The Corporation Trust Company.

ARTICLE THREE

The nature of the business or purposes to be conducted or promoted is to engage in any lawful act or activity for which corporations may be organized under the General Corporation Law of the State of Delaware.

ARTICLE FOUR

The total number of shares of stock which the corporation has authority to issue is one thousand (1,000) shares of Common Stock, with a par value of $0.01 per share.

ARTICLE FIVE

The corporation is to have perpetual existence.

ARTICLE SIX

In furtherance and not in limitation of the powers conferred by statute, the board of directors of the corporation is expressly authorized to make, alter or repeal the bylaws of the corporation.

ARTICLE SEVEN

Meetings of stockholders may be held within or without the State of Delaware, as the bylaws of the corporation may provide. The books of the corporation may be kept outside the State of Delaware at such place or places as may be designated from time to time by the board of directors or in the bylaws of the corporation. Election of directors need not be by written ballot unless the bylaws of the corporation so provide.

ARTICLE EIGHT

1. Indemnification of Officers, Directors and Others. The corporation shall indemnify to the fullest extent authorized or permitted by law (as now or hereafter in effect) any person made, or threatened to be made, a party to or otherwise involved in any action, suit or proceeding (whether civil, criminal, administrative, investigative or otherwise) by reason of the fact that he or she, his or her testator or his or her intestate is or was a director or officer of the corporation or by reason of the fact that such director or officer, at the request of the corporation, is or was serving any other corporation, partnership, joint venture, trust, employee benefit plan or other enterprise, in any capacity. Expenses, including attorneys’ fees, incurred by any such person in connection with any such action, suit or proceeding shall be paid or reimbursed by the corporation in advance of the final disposition of such action, suit or proceeding upon receipt by it of an undertaking of such person to repay such expenses if it shall ultimately be determined that such person is not entitled to be indemnified by the corporation. A director of the corporation shall not be liable to the corporation or its stockholders for monetary damages for breach of fiduciary duty as a director, except to the extent that such exemption from liability or limitation thereof is not permitted under the General Corporation Law of the State of Delaware as currently in effect or as the same may hereafter be amended. The rights provided to any person by this Article EIGHT shall be enforceable against the corporation by such person who shall be presumed to have relied upon it in serving or continuing to serve as a director or officer as provided above. Nothing contained herein shall affect any rights to indemnification to which employees other than directors and officers may be entitled by law. No amendment or repeal of this Article EIGHT shall apply to or have any effect on any right to indemnification provided hereunder with respect to any acts or omissions occurring prior to such amendment or repeal.

2. Insurance, Indemnification Agreements and Other Matters. The corporation may purchase and maintain insurance on its own behalf and on behalf of any person who is or was a director, officer, employee, fiduciary or agent of the corporation or is or was serving at the request of the corporation as a director, officer, employee, fiduciary or agent of another corporation, partnership, joint venture, trust, employee benefit plan or other enterprise against any liability asserted against such person and incurred by such person in any such capacity, or arising out of such person’s status as such, whether or not the corporation would have the power to indemnify such person against such liability under this Article EIGHT or by law or otherwise. The corporation may create a trust fund, grant a security interest and/or use other means (including, without limitation, letters of credit, surety bonds and/or other similar arrangements), as well as enter into contracts providing for indemnification to the fullest extent authorized or permitted by law and including as part thereof any or all of the foregoing, to ensure the payment of such sums as may become necessary to effect full indemnification.

3. Nonexclusivity. The rights to indemnification and payment of expenses conferred in this Article EIGHT shall not be deemed exclusive of any other right which any person may have or hereafter acquire under any statute, this certificate of incorporation of the corporation, the bylaws of the corporation or any agreement, vote of stockholders or directors or otherwise.

2

ARTICLE NINE

The corporation expressly elects not to be governed by Section 203 of the General Corporation Law of the State of Delaware.

ARTICLE TEN

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 herein and by the laws of the State of Delaware, and all rights conferred upon stockholders herein are granted subject to this reservation.

3