AMENDED AND RESTATED CERTIFICATE OF INCORPORATION OF NEW SALLY HOLDINGS, INC.

Exhibit 4.01

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

NEW SALLY HOLDINGS, INC.

New Sally Holdings, Inc. (the “Corporation”), a corporation organized and existing by virtue of the General Corporation Law of the State of Delaware (as amended from time to time, the “DGCL”), DOES HEREBY CERTIFY:

1. That the original Certificate of Incorporation of the Corporation was filed with the Secretary of State of the State of Delaware on June 16, 2006 under the name New Sally Holdings, Inc. (the “Original Certificate of Incorporation”).

2. That this Amended and Restated Certificate of Incorporation has been duly adopted by the Board of Directors of the Corporation by unanimous written consent as of [•], 200[•], and by written consent of the sole stockholder of the Corporation dated as of [•], 200[•], in accordance with the DGCL, Sections 228, 242 and 245.

3. The Original Certificate of Incorporation is hereby amended and restated so as to read in its entirety as follows:

FIRST: The name of the Corporation is [•].

SECOND: The Corporation’s registered office in the State of Delaware is at 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.

THIRD: The nature of the business of the Corporation and its purpose 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.

FOURTH: The total number of shares of stock which the Corporation shall have authority to issue is 550,000,000 shares, consisting of: (a) 400,000,000 shares of common stock, par value $0.01 (the “Common Stock”), (b) 100,000,000 shares of Class A common stock, par value $0.01 (the “Class A Common Stock”), and (c) 50,000,000 shares of preferred stock, par value $0.01 per share (the “Preferred Stock”), issuable in one or more series as hereinafter provided. As used in this Amended and Restated Certificate of Incorporation, the term “Common Stock” shall include the Common Stock and the Class A Common Stock. Except as otherwise provided herein, all shares of Class A Common Stock and Class A Common Stock will be identical and will entitle the holders thereof to the same rights and privileges.

(a) Common Stock. Except as otherwise provided (i) by the DGCL, (ii) by Section (b) of this Article FOURTH, or (iii) by resolutions, if any, of the Board of Directors fixing the relative powers, preferences and rights and the qualifications, limitations or restrictions of the Preferred Stock, the entire voting power of the shares of the Corporation for the election of directors and for all other purposes shall be vested exclusively in the Common Stock. Each share of Common Stock shall have one vote upon all matters to be voted on by the holders of the Common Stock, and shall be entitled to participate equally in all dividends payable with respect to the Common Stock, provided that the holders of the Class A Common Stock shall not be entitled to vote on any matter or to participate in any dividend or other distribution payable with respect to the Common Stock (other than the Class A Common Stock) and contemplated by (x) the Separation Agreement, dated as of June 19, 2006, among the Corporation, Sally Holdings, Inc, New Aristotle Holdings, Inc. and Alberto-Culver Company (as amended from time to time in accordance with its terms, the “Separation Agreement”) and (y) the Investment Agreement, dated as of June 19, 2006, among Alberto-Culver Company, New Aristotle Company, Sally Holdings, Inc., New Sally Holdings, Inc. and CDRS Acquisition LLC (as amended from time to time in accordance with its terms, the “Investment Agreement”). Each share of Common Stock shall share equally, subject to the rights and preferences of the Preferred Stock (as fixed by resolutions, if any, of the Board of Directors), in all assets of the Corporation, in the event of any voluntary or involuntary liquidation, dissolution or winding up of the affairs of the Corporation, or upon any distribution of the assets of the Corporation.

(b) Preferred Stock. The Preferred Stock may be issued at any time and from time to time in one or more series. Subject to the provisions of this Amended and Restated Certificate of Incorporation, the Board of Directors is authorized to fix from time to time by resolution or resolutions the number of shares of any class or series of Preferred Stock, and to determine the voting powers, designations, preferences and relative, participating, optional or other special rights, and the qualifications, limitations and restrictions thereof, of any such class or series. Further, within the limits and restrictions stated in any resolution or resolutions of the Board of Directors originally fixing the number of shares constituting any such class or series, the Board of Directors is authorized to increase or decrease (but not below the number of shares of such class or series then outstanding) the number of shares of any such class or series subsequent to the issue of shares of that class or series.

(c) Conversion of Class A Common Stock. At 12:01 a.m. Eastern Standard time on the first day following the Closing Date (as defined in the Investment Agreement), each outstanding share of Class A Common Stock shall automatically convert into a share of Common Stock, without any action by any of the Corporation, the Board of Directors of the Corporation, the holders of Class A Common Stock or any other person and the Corporation shall not be required to

2

notify any person that such conversion has been effective. At such time, the rights of any holder with respect to shares of converted Class A Common Stock will cease and such holder will be deemed to have become the holder of an equivalent number of shares of Common Stock. Promptly upon surrender to the Corporation of a certificate or certificates for shares of converted Class A Common Stock, the Corporation will issue and deliver, in accordance with the surrendering holder’s instructions, the certificate or certificates for Common Stock issuable upon such conversion.

FIFTH: The following provisions are inserted for the management of the business and for the conduct of the affairs of the Corporation and for the purpose of creating, defining, limiting and regulating the powers of the Corporation and its directors and stockholders:

(a) Classified Board of Directors. Effective as of the Distributions Time (as defined in the Separation Agreement), the directors of the Corporation, subject to the rights of the holders of shares of any class or series of Preferred Stock, shall be classified with respect to the time for which they severally hold office, into three classes, as nearly equal in number as possible, as shall be provided in the By-Laws of the Corporation, one class (“Class I”) whose term expires at the 2007 annual meeting of stockholders, another class (“Class II”) whose term expires at the 2008 annual meeting of stockholders, and another class (“Class III”) whose term expires at the 2009 annual meeting of stockholders, with each class to hold office until its successors are elected and qualified. At each annual meeting of stockholders of the Corporation, the date of which will be fixed pursuant to the By-Laws of the Corporation, and subject to the rights of the holders of shares of any class or series of Preferred Stock, the successors of the class of directors whose term expires at that meeting shall be elected to hold office for a term expiring at the annual meeting of stockholders held in the third year following the year of their election.

(b) Removal for Cause. Effective as of the Distributions Time (as defined in the Separation Agreement), subject to the rights of holders of any class or series of Preferred Stock, if any, to elect additional directors under specified circumstances, any director may be removed at any time, but only for cause, upon the affirmative vote of the holder of the holders of a majority of the combined voting power of the then outstanding stock of the Corporation entitled to vote for the election of directors.

(c) Vacancies in the Board of Directors and newly created directorships resulting from any increase in the authorized number of directors may be filled, and directors may be removed, as provided in the By-Laws.

3

(d) The election of directors may be conducted in any manner approved by the stockholders at the time when the election is held and need not be by written ballot.

(e) To the fullest extent permitted by the DGCL, as the same exists or may hereafter be amended, 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. If the DGCL is amended after the date of the filing of this Amended and Restated Certificate of Incorporation to authorize corporate action further eliminating or limiting the personal liability of directors, then the liability of a director of the Corporation shall be eliminated or limited to the fullest extent permitted by the DGCL, as so amended from time to time. No repeal or modification of this Section (e) by the stockholders shall adversely affect any right or protection of a director of the Corporation existing by virtue of this Section (e) at the time of such repeal or modification.

(f) All corporate powers and authority of the Corporation (except as at the time otherwise provided by law, by this Amended and Restated Certificate of Incorporation or by the By-Laws) shall be vested in and exercised by the Board of Directors.

(g) The Board of Directors shall have the power without the assent or vote of the stockholders to adopt, amend, alter or repeal the By-Laws of the Corporation, except to the extent that this Amended and Restated Certificate of Incorporation otherwise provide.

(h) The Corporation shall indemnify and advance expenses to the directors of the Corporation to the fullest extent permitted by the applicable provisions of the DGCL, provided that except as otherwise provided in the By-Laws, the Corporation shall not be obligated to indemnify or advance expenses to a director of the Corporation in respect of an action, suit or proceeding (or part thereof) instituted by such director, unless such action, suit or proceeding (or part thereof) has been authorized by the Board of Directors. The rights provided by this Article FIFTH, Section (h) shall not limit or exclude any rights, indemnities or limitations of liability to which any director of the Corporation may be entitled, whether as a matter of law, under the By-Laws, by agreement, vote of the stockholders or disinterested directors, or otherwise.

SIXTH: The Corporation reserves the right to amend or repeal any provision contained in this Amended and Restated Certificate of Incorporation in the manner now or hereafter prescribed by the laws of the State of Delaware, and all rights herein conferred upon stockholders or directors are granted subject to this reservation.

4

SEVENTH: Effective as of the Distributions Time (as defined in the Separation Agreement), no corporate action of stockholders of the Corporation may be taken without a meeting and vote of stockholders.

IN WITNESS WHEREOF, the undersigned officer of the Corporation has executed this Amended and Restated Certificate of Incorporation this [•] day of [•], 200[•].

5