Exhibit 3.1

CERTIFICATE OF

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

RUTH’S HOSPITALITY GROUP, INC.

* * * *

Adopted in accordance with the provisions

of §242 and §245 of the General Corporation Law

of the State of Delaware

* * * *

The undersigned, on behalf of Ruth’s Hospitality Group, Inc., a corporation duly organized and existing under and by virtue of the General Corporation Law of the State of Delaware (the “Corporation”), DOES HEREBY CERTIFY as follows:

FIRST: That the Corporation filed its original Certificate of Incorporation with the Delaware Secretary of State on May 11, 2005 under the name of RC Merger Sub, Inc., filed a Restated Certificate of Incorporation with the Delaware Secretary of State on May 19, 2005, filed an Amended and Restated Certificate to the Certificate of Incorporation with the Delaware Secretary of State on August 1, 2005, and filed a Certificate of Amendment to the Amended and Restated Certificate of Incorporation with the Delaware Secretary of State on May 23, 2008 (as so amended and restated, the “Certificate of Incorporation”).

SECOND: That the Amended and Restated Certificate of Incorporation set forth in Exhibit A attached hereto and made a part hereof (the “Restated Certificate”), further amends, integrates and restates the Certificate of Incorporation in its entirety.

THIRD: That the Restated Certificate was duly adopted by the Board of Directors and the stockholders of the Corporation in accordance with Section 242 and Section 245 of the General Corporation Law of the State of Delaware.

* * * * *

IN WITNESS WHEREOF, the undersigned on behalf of the Corporation for the purpose of restating the Certificate of Incorporation pursuant to the General Corporation Law of the State of Delaware, under penalties of perjury does hereby declare and certify that this is the act and deed of the Corporation and the facts stated herein are true, and accordingly has hereunto signed this Certificate of Amended and Restated Certificate of Incorporation this 9th day of February, 2010.

EXHIBIT A

AMENDED AND RESTATED CERTIFICATE OF INCORPORATION

OF

RUTH’S HOSPITALITY GROUP, INC.

ARTICLE ONE

NAME

The name of the Corporation is Ruth’s Hospitality Group, Inc. (the “Corporation”).

ARTICLE TWO

REGISTERED OFFICE AND AGENT

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

ARTICLE THREE

PURPOSE

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

ARTICLE FOUR

CAPITAL STOCK

Section 1. Authorized Shares. The total number of shares of capital stock which the Corporation has authority to issue is 110,000,000 consisting of:

(a) 10,000,000 shares of initially undesignated Preferred Stock, par value $0.01 per share (“Blank Check Preferred Stock”); and

(b) 100,000,000 shares of Common Stock, par value $0.01 per share (the “Common Stock”).

Section 2. Blank Check Preferred Stock. The Blank Check Preferred Stock may be issued from time to time and in one or more series. The Board of Directors of the Corporation is authorized to determine or alter the powers, preferences and rights, and the qualifications, limitations and restrictions granted to or imposed upon any wholly unissued series of Blank Check Preferred Stock, and within the limitations or restrictions stated in any resolution or resolutions of the Board of Directors originally fixing the number of shares constituting any series of Blank Check Preferred Stock, to increase or decrease (but not below the number of shares of any such series of Preferred Stock then outstanding) the number of shares of any such series of Blank Check Preferred Stock, and to fix the number of shares of any series of Blank Check Preferred Stock. In the event that the number of shares of any series of Blank Check Preferred Stock shall be so decreased, the shares constituting such decrease shall resume the status which such shares had prior to the adoption of the resolution originally fixing the number of shares of such series of Blank Check Preferred Stock subject to the requirements of applicable law.

Section 3. Common Stock. Except as required by applicable law, the rights and privileges of the Common Stock shall be subject to the powers, preferences and rights of any shares of Blank Check Preferred Stock as authorized by the Board of Directors. Except as otherwise provided in this Section 3 or as otherwise required by applicable law, all shares of Common Stock shall be identical in all respects and shall entitle the holders thereof to the same rights and privileges, and shall rank equally, share ratably and be identical in all respects as to all matters.

(a) Voting Rights. Except as otherwise provided in this Section 3 or as otherwise required by applicable law, the holders of Common Stock shall be entitled to one vote per share on all matters to be voted on by the Corporation’s shareholders.

(b) Dividends. As and when dividends are declared or paid thereon, whether in cash, property or securities of the Corporation, the holders of Common Stock shall be entitled to participate in such dividends ratably on a per share basis.

(c) Liquidation. The holders of the Common Stock shall be entitled to participate ratably on a per share basis in all distributions to the holders of Common Stock in any liquidation, dissolution or winding up of the Corporation.

(d) Registration of Transfer. The Corporation shall keep at its principal office (or such other place as the Corporation reasonably designates) a register for the registration of shares of Common Stock. Upon the surrender at such place of any certificate representing shares of Common Stock, the Corporation shall, at the request of the record holder of such certificate. execute and deliver (at the Corporation’s expense) a new certificate or certificates in exchange therefor representing in the aggregate the number of shares of such stock represented by the surrendered certificate and the Corporation shall forthwith cancel such surrendered certificate. Each such new certificate shall be registered in such name and shall represent such number of shares of Common Stock as is requested by the holder of the surrendered certificate and shall be substantially identical in form to the surrendered certificate. The issuance of new certificates shall be made without charge to the holders of the surrendered certificates for any issuance tax in respect thereof or other cost incurred by the Corporation in connection with such issuance.

(e) Replacement. Upon receipt of evidence reasonably satisfactory to the Corporation (provided, that an affidavit of the registered holder will be satisfactory) of the ownership and the loss, theft, destruction or mutilation of any certificate evidencing one or more shares of Common Stock, and in the case of any such loss, theft or destruction, upon receipt of indemnity reasonably satisfactory to the Corporation (provided that if the holder is a financial institution or other institutional investor its own agreement will be satisfactory), or, in the case of any such mutilation upon surrender of such certificate, the Corporation shall (at its expense) execute and deliver in lieu of such certificate of like kind representing the number of shares of such stock represented by such lost, stolen, destroyed or mutilated certificate and dated the date of such lost, stolen, destroyed or mutilated certificate.

(f) Notices. All notices referred to herein shall be in writing, and shall be delivered by registered or certified mail, return receipt requested, postage prepaid, and shall be deemed to have been given when so mailed (i) to the Corporation at its principal executive offices and (ii) to any shareholder at such holder’s address as it appears in the stock records of the Corporation (unless otherwise specified in a written notice to the Corporation by such holder).

(g) Amendment and Waiver. No amendment or waiver of any provision of this Section 3 shall be effective without the prior written consent of the holders of a majority of the then outstanding shares of Common Stock voting as a single class. For purposes of votes on amendments and waivers to this Section 3, each share of Common Stock shall be entitled to one vote.

ARTICLE FIVE

DURATION

The Corporation is to have perpetual existence.

ARTICLE SIX

BOARD OF DIRECTORS

Section 1. Number of Directors. The number of directors which shall constitute the Board of Directors shall be fixed from time to time by resolution adopted by the affirmative vote of a majority of the total number of directors then in office.

Section 2. Election and Term of Office. The directors shall be elected by a plurality of the votes of the shares of capital stock of the Corporation present in person or represented by proxy at the meeting and entitled to vote in the election of directors. The directors shall be elected and shall hold office only in this manner, except as provided in Section 3 of this Article Six. Each director shall hold office until a successor is duly elected and qualified or until his or her earlier death, resignation or removal. Elections of directors need not be by written ballot unless the Bylaws of the Corporation shall so provide.

2

Section 3. Newly-Created Directorships and Vacancies. Newly created directorships resulting from any increase in the number of directors or any vacancies in the Board of Directors resulting from death, resignation, retirement, disqualification, removal from office or any other cause may be filled, so long as there is at least one remaining director, only by the Board of Directors, provided that a quorum is then in office and present, or by a majority of the directors then in office, if less than a quorum is then in office, or by the sole remaining director. Directors elected to fill a newly created directorship or other vacancies shall hold office until such director’s successor has been duly elected and qualified or until his or her earlier death, resignation or removal as hereinafter provided.

Section 4. Removal of Directors. Any director may be removed from office at any time for cause, at a meeting called for that purpose, but only by the affirmative vote of the holders of at least 66 ²/ 3% of the voting power of all outstanding shares of capital stock of the Corporation entitled to vote generally in the election of directors, voting together as a single class.

Section 5. Bylaws. The Board of Directors is expressly authorized to adopt, amend or repeal the bylaws of the Corporation. Notwithstanding the foregoing and anything contained in this Amended and Restated Certificate of Incorporation to the contrary, the bylaws of the Corporation shall not be amended or repealed by the stockholders, and no provision inconsistent therewith shall be adopted by the stockholders, without the affirmative vote of the holders of 66 ²/ 3% of the voting power of all outstanding shares of capital stock of the Corporation entitled to vote generally in the election of directors.

ARTICLE SEVEN

LIMITATION OF LIABILITY AND INDEMNIFICATION

Section 1. Limitation of Liability.

(a) To the fullest extent permitted by the Delaware General Corporation Law as it now exists or may hereafter be amended (but, in the case of any such amendment, only to the extent that such amendment permits the Corporation to provide broader indemnification rights than permitted prior thereto), no director of the Corporation shall be liable to the Corporation or its stockholders for monetary damages arising from a breach of fiduciary duty owed to the Corporation or its stockholders.

(b) Any repeal or modification of the foregoing paragraph by the stockholders of the Corporation shall not adversely affect any right or protection of a director of the Corporation existing at the time of such repeal or modification.

Section 2. Right to Indemnification. Each person who was or is made a party or is threatened to be made a party to or is otherwise involved (including involvement as a witness) in any action, suit or proceeding, whether civil, criminal, administrative or investigative (a “proceeding”), by reason of the fact that he or she is or was a director or officer of the Corporation or, while a director or officer of the Corporation, is or was serving at the request of the Corporation as a director, officer, employee or agent of another corporation or of a partnership, joint venture, trust or other enterprise, including service with respect to an employee benefit plan (an “indemnitee”), whether the basis of such proceeding is alleged action in an official capacity as a director or officer or in any other capacity while serving as a director or officer, shall be indemnified and held harmless by the Corporation to the fullest extent authorized by the Delaware General Corporation Law, as the same exists or may hereafter be amended (but, in the case of any such amendment, only to the extent that such amendment permits the Corporation to provide broader indemnification rights than permitted prior thereto), against all expense, liability and loss (including attorneys’ fees and related disbursements, judgments, fines, excise taxes or penalties under the Employee Retirement Income Security Act of 1974, as amended from time to time (“ERISA”), penalties and amounts paid or to be paid in settlement) reasonably incurred or suffered by such indemnitee in connection therewith and such indemnification shall continue as to an indemnitee who has ceased to be a director, officer, employee or agent and shall inure to the benefit of the indemnitee’s heirs, executors and administrators; provided, however, that, except as provided in

3

Section 3 of this Article Seven with respect to proceedings to enforce rights to indemnification, the Corporation shall indemnify any such indemnitee in connection with a proceeding (or part thereof) initiated by such indemnitee only if such proceeding (or part thereof) was authorized by the Board of Directors of the Corporation. The right to indemnification conferred in this Section 2 of this Article Seven shall be a contract right and shall include the obligation of the Corporation to pay the expenses incurred in defending any such proceeding in advance of its final disposition (an “advance of expenses”); provided, however, that an advance of expenses incurred by an indemnitee shall be made only upon delivery to the Corporation of an undertaking (an “undertaking”), by or on behalf of such indemnitee, to repay all amounts so advanced if it shall ultimately be determined by final judicial decision from which there is no further right to appeal (a “final adjudication”) that such indemnitee is not entitled to be indemnified for such expenses under this Section 2 or otherwise. The Corporation may, by action of its Board of Directors, provide indemnification to employees and agents of the Corporation with the same or lesser scope and effect as the foregoing indemnification of directors and officers.

Section 3. Procedure for Indemnification. Any indemnification of a director or officer of the Corporation or advance of expenses under Section 2 of this Article Seven shall be made promptly, and in any event within forty-five days (or, in the case of an advance of expenses, twenty days, provided that the director or officer has delivered the undertaking contemplated by Section 2 of this Article Seven), upon the written request of the director or officer. If a determination by the Corporation that the director or officer is entitled to indemnification pursuant to this Article Seven is required, and the Corporation fails to respond within sixty days to a written request for indemnity, the Corporation shall be deemed to have approved the request. If the Corporation denies a written request for indemnification or advance of expenses, in whole or in part, or if payment in full pursuant to such request is not made within forty-five days (or, in the case of an advance of expenses, twenty days, provided that the director or officer has delivered the undertaking contemplated by Section 2 of this Article Seven), the right to indemnification or advances as granted by this Article Seven shall be enforceable by the director or officer in any court of competent jurisdiction. Such person’s costs and expenses incurred in connection with successfully establishing his or her right to indemnification, in whole or in part, in any such action shall also be indemnified by the Corporation. It shall be a defense to any such action (other than an action brought to enforce a claim for the advance of expenses where the undertaking required pursuant to Section 2 of this Article Seven, if any, has been tendered to the Corporation) that the claimant has not met the standards of conduct which make it permissible under the Delaware General Corporation Law for the Corporation to indemnify the claimant for the amount claimed, but the burden of such defense shall be on the Corporation. Neither the failure of the Corporation (including its Board of Directors, independent legal counsel or its stockholders) to have made a determination prior to the commencement of such action that indemnification of the claimant is proper in the circumstances because he or she has met the applicable standard of conduct set forth in the Delaware General Corporation Law, nor an actual determination by the Corporation (including its Board of Directors, independent legal counsel or its stockholders) that the claimant has not met such applicable standard of conduct, shall be a defense to the action or create a presumption that the claimant has not met the applicable standard of conduct. The procedure for indemnification of other employees and agents for whom indemnification is provided pursuant to Section 2 of this Article Seven shall be the same procedure set forth in this Section 3 for directors or officers, unless otherwise set forth in the action of the Board of Directors providing indemnification for such employee or agent.

Section 4. Insurance. 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 or agent of the Corporation or was serving at the request of the Corporation as a director, officer, employee or agent of another corporation, partnership, joint venture, trust or other enterprise against any expense, liability or loss asserted against him or her and incurred by him or her in any such capacity, whether or not the Corporation would have the power to indemnify such person against such expenses, liability or loss under the Delaware General Corporation Law.

Section 5. Service for Subsidiaries. Any person serving as a director, officer, employee or agent of another corporation, partnership, limited liability company, joint venture or other enterprise, at least 50% of whose equity interests are owned by the Corporation (a “subsidiary” for this Article Seven) shall be conclusively presumed to be serving in such capacity at the request of the Corporation.

Section 6. Reliance. Persons who after the date of the adoption of this provision become or remain directors or officers of the Corporation or who, while a director or officer of the Corporation, become or remain a director, officer, employee or agent of a subsidiary, shall be conclusively presumed to have relied on the rights to indemnity,

4

advance of expenses and other rights contained in this Article Seven in entering into or continuing such service. The rights to indemnification and to the advance of expenses conferred in this Article Seven shall apply to claims made against an indemnitee arising out of acts or omissions which occurred or occur both prior and subsequent to the adoption hereof.

Section 7. Non-Exclusivity of Rights. The rights to indemnification and to the advance of expenses conferred in this Article Seven shall not be exclusive of any other right which any person may have or hereafter acquire under this Amended and Restated Certificate of Incorporation or under any statute, by-law, agreement, vote of stockholders or disinterested directors or otherwise.

Section 8. Merger or Consolidation. For purposes of this Article Seven, references to the “Corporation” shall include, in addition to the resulting Corporation, any constituent Corporation (including any constituent of a constituent) absorbed in a consolidation or merger which, if its separate existence had continued, would have had power and authority to indemnify its directors, officers and employees or agents, so that any person who is or was a director, officer, employee or agent of such constituent Corporation, or is or was serving at the request of such constituent Corporation as a director, officer, employee or agent of another Corporation, partnership, joint venture, trust or other enterprise, shall stand in the same position under this Article Seven with respect to the resulting or surviving Corporation as he or she would have with respect to such constituent Corporation if its separate existence had continued.

Section 9. Savings Clause. If this Article Seven or any portion hereof shall be invalidated on any ground by any court of competent jurisdiction, then the Corporation shall nevertheless indemnify each person entitled to indemnification under Section 2 of this Article Seven as to all expense, liability and loss (including attorneys’ fees and related disbursements, judgments, fines, ERISA excise taxes and penalties, penalties and amounts paid or to be paid in settlement) actually and reasonably incurred or suffered by such person and for which indemnification is available to such person pursuant to this Article Seven to the full extent permitted by any applicable portion of this Article Seven that shall not have been invalidated and to the full extent permitted by applicable law.

ARTICLE EIGHT

ACTION BY WRITTEN CONSENT/SPECIAL MEETINGS OF STOCKHOLDERS

If the Corporation’s Common Stock is registered under Section 12 of the Securities Exchange Act of 1934, as amended: (i) the stockholders of the Corporation may not take any action by written consent in lieu of a meeting, and must take any actions at a duly called annual or special meeting of stockholders and the power of stockholders to consent in writing without a meeting is specifically denied and (ii) special meetings of stockholders of the Corporation may be called only by either the Board of Directors pursuant to a resolution adopted by the affirmative vote of the majority of the total number of directors then in office or by the chairman of the Board of Directors.

ARTICLE NINE

CERTAIN TRANSACTIONS

Section 1. Certain Acknowledgments. In recognition and anticipation that, (i) the directors, officers, members, managers and/or employees of Madison Dearborn Capital Parters III, LP and Madison Dearborn Partners, LLC or affiliates and investment funds of such entities (collectively, “Madison Dearborn”) may serve as directors and/or officers of the Corporation, (ii) Madison Dearborn may engage in the same or similar activities or related lines of business as those in which the Corporation, directly or indirectly, may engage and/or other business activities that overlap with or compete with those in which the Corporation, directly or indirectly, may engage, (iii) non-employee directors of the Corporation may engage in the same or similar activities or related lines of business as those in which the Corporation, directly or indirectly, may engage and/or other business activities that overlap with or compete with those in which the Corporation, directly or indirectly may engage, and (iv) the Corporation and its subsidiaries may engage in material business transactions with Madison Dearborn and that the Corporation is expected to benefit therefrom, the provisions of this Article Nine are set forth to regulate and define the conduct of certain affairs of the Corporation as they may involve either any non-employee director or Madison Dearborn and its directors, officers, members, managers and/or employees, and the powers, rights, duties and liabilities of the Corporation and its officers, directors and stockholders in connection therewith.

5

Section 2. Competition and Corporate Opportunities. Neither Madison Dearborn nor any non-employee director shall have any duty to refrain from engaging directly or indirectly in the same or similar business activities or lines of business as the Corporation or any of its subsidiaries. In the event that Madison Dearborn or any non-employee director acquires knowledge of a potential transaction or matter which may be a corporate opportunity for themselves and the Corporation or any of its subsidiaries, neither the Corporation nor any of its subsidiaries shall have any expectancy in such corporate opportunity, and neither Madison Dearborn nor any non-employee director shall have any duty to communicate or offer such corporate opportunity to the Corporation or any of its subsidiaries and may pursue or acquire such corporate opportunity for themselves or direct such corporate opportunity to another person.

Section 3. Allocation of Corporate Opportunities. In the event that a director of the Corporation who is not an employee of the Corporation acquires knowledge of a potential transaction or matter which may be a corporate opportunity for the Corporation or any of its subsidiaries and such non-employee director, neither the Corporation nor any of its subsidiaries shall have any expectancy in such corporate opportunity unless such corporate opportunity is expressly offered to such non-employee director solely in his or her capacity as a director of the Corporation.

Section 4. Agreements and Transactions with Madison Dearborn. In the event that Madison Dearborn enters into an agreement or transaction with the Corporation or any of its subsidiaries, a director or officer of the Corporation who is also a director, officer, member, manager and/or employee of Madison Dearborn shall have fully satisfied and fulfilled the fiduciary duty of such director or officer to the Corporation and its stockholders with respect to such agreement or transaction, if:

(a) The agreement or transaction was approved, after being made aware of the material facts of the relationship between each of the Corporation or subsidiary thereof and Madison Dearborn and the material terms and facts of the agreement or transaction, by (i) an affirmative vote of a majority of the members of the Board of Directors of the Corporation who are not persons or entities with a material financial interest in the agreement or transaction (“Interested Persons”) or (ii) an affirmative vote of a majority of the members of a committee of the Board of Directors of the Corporation consisting of members who are not Interested Persons;

(b) The agreement or transaction was fair to the Corporation at the time the agreement or transaction was entered into by the Corporation; or

(c) The agreement or transaction was approved by an affirmative vote of a majority of the shares of the Corporation’s Common Stock entitled to vote, excluding Madison Dearborn and any Interested Person; provided that if no Common Stock is then outstanding a majority of the voting power of the Corporation’s capital stock entitled to vote, excluding Madison Dearborn and any Interested Person.

Section 5. Amendment of this Article. Notwithstanding anything to the contrary elsewhere contained in this Amended and Restated Certificate of Incorporation, the affirmative vote of the holders of at least 80% of the voting power of all shares of Common Stock then outstanding, shall be required to alter, amend or repeal, or to adopt any provision inconsistent with, this Article Nine.

Section 6. Deemed Notice. Any person or entity purchasing or otherwise acquiring any interest in any shares of the Corporation shall be deemed to have notice or and to have consented to the provisions of this Article Nine.

ARTICLE TEN

AMENDMENT

Subject to Article Four hereof, the Corporation reserves the right to amend, alter, change or repeal any provision contained in this Amended and Restated 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. Notwithstanding any other provision of this Amended and Restated Certificate of Incorporation or the Bylaws of the Corporation, and notwithstanding the fact that a lesser percentage or separate

6

class vote may be specified by law, this Amended and Restated Certificate of Incorporation, the Bylaws of the Corporation or otherwise, but in addition to any affirmative vote of the holders of any particular class or series of the capital stock set forth in Articles Four or Nine or as required by law, this Amended and Restated Certificate of Incorporation, the Bylaws of the Corporation or otherwise, the affirmative vote of the holders of at least 66 ²/3% of the voting power of all outstanding shares of capital stock of the Corporation entitled to vote generally in the election of directors, shall be required to adopt any provision inconsistent with, to amend or repeal any provision of, or to adopt a bylaw inconsistent with, Articles Six, Seven, Eight and Ten of this Amended and Restated Certificate of Incorporation.

ARTICLE ELEVEN

SECTION 203 OF THE DELAWARE GENERAL CORPORATION LAW

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

7