AMENDED AND RESTATED TERMINATION AGREEMENT

Exhibit 10.1

AMENDED AND RESTATED TERMINATION AGREEMENT

This Amended and Restated Termination Agreement (this “Agreement”) is entered into as of November 5, 2012 (the “Agreement Date”) by and between Sally Beauty Holdings, Inc., a Delaware corporation (“SBH”) and Gary G. Winterhalter (the “Executive”).  This Agreement amends and restates the original Termination Agreement by and among Alberto-Culver Company, a Delaware corporation, Sally Holdings, Inc., a Delaware corporation (“Sally Holdings”), and the Executive, dated as of June 19, 2006, as amended on January 24, 2007 (the “Original Agreement”).  As required by the Original Agreement, this amended and restated version of the Agreement has been consented to by Sally Holdings LLC, the successor to Sally Holdings, Inc. and CDRS Acquisition LLC.

WHEREAS, the Executive currently serves as the Chief Executive Officer of SBH, and SBH desires to assume the rights and obligations of Sally Holdings under the Agreement, and

WHEREAS, the parties desire to further amend the Agreement (i) to reflect the passage of more than two years since the spinoff of Sally Holdings from Alberto-Culver Company (defined as the “Effective Time” in the Original Agreement), (ii) to reflect the assignment to and assumption by SBH of the rights and obligations of Sally Holdings under the Agreement as they relate to the Executive, (iii) to update the provisions of the Agreement relating to Section 409A of the Internal Revenue Code, including protective language relating to the timing of a release of claims as discussed in Internal Revenue Service Notices 2010-6 and 2010-80, (iv) to remove the requirement that CDRS Acquisition LLC consent to further amendments to the Agreement, if any; (v) to update Schedule I to the Agreement as appropriate to accommodate the release timing language and to extend the post-termination medical and dental insurance coverage, and (vi) to delete Exhibit A, as the parties have already entered into the Severance Agreement referred to therein; and

WHEREAS, the Agreement currently provides that the Agreement cannot be amended except by a writing executed by the Executive, Sally Holdings and CDRS Acquisition LLC;

NOW, THEREFORE, in consideration of the premises and mutual covenants and agreements contained herein, the parties hereby amend and restate the Agreement as follows:

1. Termination of Employment.

(a) SBH and the Executive agree that in the event of the termination of the Executive’s employment without Cause by SBH or by the Executive for Good Reason on or after the Agreement Date, the Executive shall be entitled to the payments and benefits set forth in Schedule I hereto.  In the event that the Executive retires from employment at any time with the prior approval of the Board of Directors of SBH, the Executive shall be entitled to the medical and dental benefits and payments set forth in the second paragraph of Schedule I hereto, but not to the other benefits described in Schedule I.

(b) SBH and the Executive are parties to that certain Amended and Restated Severance Agreement, dated as of November 5, 2012, which provides certain severance payments and benefits in the event of the termination of the Executive’s employment without Cause by SBH or by the Executive for Good Reason within two years following a change in control of SBH (the “Severance Agreement”).  If the Executive shall be entitled to any payments or benefits pursuant to the Severance Agreement, then the Executive shall not be entitled to any payments or benefits under this Agreement.

(c) For purposes of Section 1(a), the term “Cause” means (1) a material breach by the Executive of those duties and responsibilities of the Executive which do not differ in any material respect from the duties and responsibilities of the Executive during the six-month period immediately prior to the Agreement Date (other than as a result of incapacity due to physical or mental illness) which is demonstrably willful and deliberate on the Executive’s part, which is committed in bad faith or without reasonable belief that such breach is in the best interests of SBH and which is not remedied in a reasonable period of time after receipt of written notice from SBH specifying such breach, or (2) the commission by the Executive of a felony involving moral turpitude.

(d) For purposes of Section 1(a), “Good Reason” means, without the Executive’s consent, the occurrence of any of the following circumstances after the Agreement Date unless such circumstances are fully corrected prior to the expiration of the fifteen (15) calendar day period following delivery to SBH of the Executive’s notice of intention to terminate his employment for Good Reason describing such circumstances in reasonable detail (which notice must be given no later than 90 days after the occurrence of such event):

(A) any of (1) the assignment to the Executive of any duties inconsistent in any material respect with the Executive’s position(s), duties, responsibilities or status immediately prior to the Agreement Date, (2) a change in the Executive’s reporting responsibilities as in effect immediately prior to the Agreement Date or (3) any removal or involuntary termination of the Executive otherwise than as expressly permitted by this Agreement;

(B) a reduction in the Executive’s rate of annual base salary as in effect immediately prior to the Agreement Date or as the same may be increased from time to time thereafter:

(C) any requirement that the Executive be based anywhere other than within a 20 mile radius of the facility where the Executive is located as of the Agreement Date; or

(D) the failure of SBH or any of its affiliated companies to (1) continue in effect any employee benefit plan or compensation plan in which the Executive is participating immediately prior to the Agreement Date, unless the Executive is permitted to participate in other plans providing the Executive with substantially comparable benefits, or the taking of any action by SBH or any of its affiliated companies which would adversely affect the Executive’s participation in or materially reduce the Executive’s benefits under any such plan, (2) provide the Executive and the Executive’s dependents welfare benefits in accordance with the plans, practices, programs and policies as in effect generally at any time with respect

2

to the other peer executives of SBH, (3) provide fringe benefits in accordance with the plans, practices, programs and policies as in effect generally at any time with respect to other peer executives of SBH, (4) provide the Executive with paid vacation in accordance with the plans, policies, programs and practices as in effect generally at any time with respect to other peer executives of SBH, or (5) reimburse the Executive promptly for all reasonable employment expenses incurred by the Executive in accordance with the policies, practices and procedures as in effect generally at any time with respect to other peer executives of SBH.

2. Limitations on Payments to the Executive. Solely for the purposes of the computation of benefits under this Agreement and notwithstanding any other provisions hereof, payments to the Executive under this Agreement shall be reduced (but not below zero) so that the present value, as determined in accordance with Section 280G(d)(4) of the Internal Revenue Code of 1986, as amended (the “Code”), of such payments plus any other payments that must be taken into account for purposes of any computation relating to the Executive under Section 280G(b)(2)(A)(ii) of the Code, shall not, in the aggregate, exceed 2.99 times the Executive’s “base amount,” as such term is defined in Section 280G(b)(3) of the Code. Notwithstanding any other provision hereof, no reduction in payments under the limitation contained in the immediately preceding sentence shall be applied to payments hereunder which do not constitute “excess parachute payments” within the meaning of the Code. Any payments in excess of the limitation of this Section 2 or otherwise determined to be “excess parachute payments” made to the Executive hereunder shall be deemed to be overpayments which shall constitute an amount owing from the Executive to SBH with interest from the date of receipt by the Executive to the date of repayment (or offset) at the applicable federal rate under Section 1274(d) of the Code, compounded semi-annually, which shall be payable upon demand; provided, however, that no repayment shall be required under this sentence if in the written opinion of tax counsel satisfactory to the Executive and delivered to the Executive and SBH such repayment does not allow such overpayment to be excluded for federal income and excise tax purposes from the Executive’s income for the year of receipt or afford the Executive a compensating federal income tax deduction for the year of repayment.

3. Withholding Taxes. SBH may withhold from all payments due to the Executive (or the Executive’s estate or beneficiaries) hereunder all taxes which, by applicable federal, state, local or other law, are required to be withheld therefrom.

4. Agreement Date; Termination of Agreement. This Agreement shall be effective on the Agreement Date.

5. Scope of Agreement. Nothing in this Agreement shall be deemed to entitle the Executive to continued employment with SBH.

6. Successors; Binding Agreement.

(a) This Agreement shall inure to the benefit of and be enforceable by SBH and its successors and assigns, and by the Executive and the Executive’s personal or legal representatives, executors, administrators, successors, heirs, distributees, devisees and

3

legatees. If the Executive shall die after terminating employment pursuant to Section 1(a) while any amounts would be payable to the Executive hereunder had the Executive continued to live, all such amounts, unless otherwise provided herein, shall be paid in accordance with the terms of this Agreement to such person or persons appointed in writing by the Executive to receive such amounts or, if no person is so appointed, to the Executive’s estate.

(b) This Agreement shall not be terminated by any merger or consolidation of SBH whereby SBH is or is not the surviving or resulting corporation or as a result of any transfer of all or substantially all of the assets of SBH. In the event of any such merger, consolidation or transfer of assets, the provisions of this Agreement shall be binding upon the surviving or resulting corporation or the person or entity to which such assets are transferred.

7. Notices. (a) For purposes of this Agreement, all notices and other communications required or permitted hereunder shall be in writing and shall be duly given upon receipt when delivered by United States mail, certified and return receipt requested, postage prepaid, addressed (i) if to the Executive, to the Executive’s most recent address as it appears in the records of SBH, if to SBH, to Sally Beauty Holdings, Inc., 3001 Colorado Boulevard, Denton, TX 76210, attention of the General Counsel, or (ii) to such other address as any party may have furnished to the other parties in writing in accordance herewith.

(b) A written notice of the Executive’s termination of employment by SBH or by the Executive, as the case may be, shall (i) set forth in reasonable detail the facts and circumstances claimed to provide a basis for termination of the Executive’s employment and (ii) specify the termination date (which date shall be not less than 15 days after the giving of such notice). The failure by the Executive or SBH to set forth in such notice any fact or circumstance which contributes to a showing of Good Reason or Cause shall not waive any right of the Executive or SBH hereunder or preclude the Executive or SBH from asserting such fact or circumstance in enforcing the rights of the Executive or SBH hereunder.

8. Employment with Subsidiaries. Employment with SBH for purposes of this Agreement shall include employment with SBH or any corporation or other entity in which SBH has a direct or indirect ownership interest of 50% or more of the total combined voting power of the then outstanding securities of such corporation or other entity entitled to vote generally in the election of directors.

9. Governing Law; Validity. The interpretation, construction and performance of this Agreement shall be governed by and construed and enforced in accordance with the internal laws of the State of Delaware without regard to the principle of conflicts of laws. The invalidity or unenforceability of any provision of this Agreement shall not affect the validity or enforceability of any other provision of this Agreement, which other provisions shall remain in full force and effect.

10. Counterparts. This Agreement may be executed in two or more counterparts, all of which shall be deemed to be an original and all of which together shall constitute one and the same instrument.

4

11. Miscellaneous. No provision of this Agreement may be modified or waived unless such modification or waiver is agreed to in writing and signed by the Executive and by a duly authorized officer of SBH. No waiver by any party hereto at any time of any breach by any other party hereto of, or compliance with, any condition or provision of this Agreement to be performed by such other party shall be deemed a waiver of similar or dissimilar provisions or conditions at the same or at any prior or subsequent time. Failure by the Executive or SBH to insist upon strict compliance with any provision of this Agreement or to assert any right the Executive or SBH may have hereunder, including, without limitation, the right of the Executive to terminate employment for Good Reason, shall not be deemed to be a waiver of such provision or right or any other provision or right under this Agreement. The rights of, and benefits payable to, the Executive (or the Executive’s estate or beneficiaries) pursuant to this Agreement are in addition to any rights of, or benefits payable to, the Executive (or the Executive’s estate or beneficiaries) under any other employee benefit plan or compensation program of SBH.

12. Code Section 409A

(a)                General.  This Agreement shall be interpreted and administered in a manner so that any amount or benefit payable hereunder shall be paid or provided in a manner that is either exempt from or compliant with the requirements Section 409A of the Code and applicable advice and regulations issued thereunder. Nevertheless, the tax treatment of the benefits provided under the Agreement is not warranted or guaranteed.  Neither SBH nor its directors, officers, employees or advisers (other than the Executive) shall be held liable for any taxes, interest, penalties or other monetary amounts owed by the Executive as a result of the application of Section 409A of the Code.

(b)                Definitional Restrictions.  Notwithstanding anything in this Agreement to the contrary, to the extent that any amount or benefit that would constitute non-exempt “deferred compensation” for purposes of Section 409A of the Code would otherwise be payable or distributable hereunder by reason of the Executive’s termination of employment, such amount or benefit will not be payable or distributable to the Executive by reason of such circumstance unless the circumstances giving rise to such termination of employment meet any description or definition of “separation from service” in Section 409A of the Code and applicable regulations (without giving effect to any elective provisions that may be available under such definition).  This provision does not prohibit the vesting of any amount upon a termination of employment, however defined.  If this provision prevents the payment or distribution of any amount or benefit, such payment or distribution shall be made on the date, if any, on which an event occurs that constitutes a Section 409A-compliant “separation from service” or such later date as may be required by subsection (c) below.

(c)                 Six-Month Delay in Certain Circumstances.  Notwithstanding anything in this Agreement to the contrary, if any amount or benefit that would constitute non-exempt “deferred compensation” for purposes of Section 409A of the Code would otherwise be payable or distributable under this Agreement by reason of the Executive’s separation from service during a period in which he is a Specified Employee (as defined below), then, subject to any permissible acceleration of payment by SBH under Treas.

5

Reg. Section 1.409A-3(j)(4)(ii) (domestic relations order), (j)(4)(iii) (conflicts of interest), or (j)(4)(vi) (payment of employment taxes):

(1)                if the payment or distribution is payable in a lump sum, the Executive’s right to receive payment or distribution of such non-exempt deferred compensation will be delayed until the earlier of the Executive’s death or the first day of the seventh month following the Executive’s separation from service; and

(2)                if the payment or distribution is payable over time, the amount of such non-exempt deferred compensation that would otherwise be payable during the six-month period immediately following the Executive’s separation from service will be accumulated and the Executive’s right to receive payment or distribution of such accumulated amount will be delayed until the earlier of the Executive’s death or the first day of the seventh month following the Executive’s separation from service, whereupon the accumulated amount will be paid or distributed to the Executive on such date and the normal payment or distribution schedule for any remaining payments or distributions will resume.

For purposes of this Agreement, the term “Specified Employee” has the meaning given such term in Code Section 409A and the final regulations thereunder (“Final 409A Regulations”), provided, however, that, as permitted in the Final 409A Regulations, SBH’s Specified Employees and its application of the six-month delay rule of Code Section 409A(a)(2)(B)(i) shall be determined in accordance with rules adopted by the Board or a committee thereof, which shall be applied consistently with respect to all nonqualified deferred compensation arrangements of SBH, including this Agreement.

(d)                Timing of Release of Claims.  Whenever in this Agreement a payment or benefit is conditioned on the Executive’s execution and non-revocation of a release of claims, such release must be executed and all revocation periods shall have expired within 60 days after the Executive’s termination of employment; failing which such payment or benefit shall be forfeited.  If such payment or benefit constitutes non-exempt deferred compensation, and if such 60-day period begins in one calendar year and ends in the next calendar year, the payment or benefit shall not be made or commence before the second such calendar year, even if the release becomes irrevocable in the first such calendar year.  In other words, the Executive is not permitted to influence the calendar year of payment based on the timing of his signing of the release.

(e)                 Permitted Acceleration.  SBH shall have the sole authority to make any accelerated distribution permissible under Treas. Reg. Section 1.409A-3(j)(4) to the Executive of deferred amounts, provided that such distribution meets the requirements of Treas. Reg. Section 1.409A-3(j)(4).

(f)                  409A Amendments.  SBH shall have the right to make such amendments, if any, to this Agreement as shall be necessary to avoid the application of Section 409A(a)(1) of the Code to the payments of amounts pursuant to this Agreement, and shall give prompt notice of any such amendment to the Executive.  If SBH defers payments to the Executive pursuant to this Section 12, then SBH shall provide the Executive with prompt written notice thereof, including reasonable explanation and the estimated date on

6

which it has determined it is permitted to make the payments deferred under this Section 12.

13. Amendment. Except as provided in Section 12, this Agreement cannot be amended except pursuant to a writing signed by SBH, or its successor, and the Executive.

IN WITNESS WHEREOF, SBH has caused this Agreement to be executed by its duly authorized officer and the Executive has executed this Agreement as of the dates set forth below.

7

SCHEDULE I

TO

TERMINATION AGREEMENT

Lump Sum Payment

Within 30 days following the date of termination the Executive’s employment in accordance with Section 1(a) of the Agreement (the “Date of Termination”) (or such later date as may be required by Section 12 of the Agreement), provided that SBH has received a customary release (which release shall extend to all claims against SBH and its affiliates and agents) signed by the Executive and not revoked within the permitted revocation period, SBH shall pay to the Executive a lump sum payment equal to two (2) times the Executive’s annual base salary at the Date of Termination, plus two (2) times the average of the dollar amount of the Executive’s actual or annualized (for any fiscal year consisting of less than 12 full months) annual bonus, paid or payable, including by reason of any deferral, to the Executive by SBH and its affiliated companies in respect of the five fiscal years of SBH immediately preceding the fiscal year in which the Date of Termination occurs.

Benefits

Medical and Dental Insurance Continuation. For a period of 18 months commencing on the Date of Termination (the “Initial Coverage Period”), SBH shall continue to keep in full force and effect all policies of medical and dental insurance with respect to the Executive and his dependents with the same level of coverage, upon the same terms and otherwise to the same extent as the Executive and his dependents were participating in such policies as in effect immediately prior to the Date of Termination (such coverage, the “Date of Termination Coverage”) or, if more favorable to the Executive, as provided generally with respect to other peer executives of SBH and its affiliated companies, and SBH and the Executive shall share the costs of the continuation of such insurance coverage in the same proportion as such costs were shared immediately prior to the Date of Termination. On the first day of the month following the expiration of the Initial Coverage Period, SBH shall pay to Executive a lump sum cash payment equal to (i) SBH’s full monthly cost for Date of Termination Coverage (i.e., excluding the Executive’s cost of such coverage) on the last day of the Initial Coverage Period times (ii) the greater of six or the number of months then remaining until the Executive becomes eligible for Medicare coverage (the “Extended Coverage Period”).  SBH shall continue the Executive’s eligibility for COBRA-type medical and dental benefits for the Extended Coverage Period. SBH’s obligation to continue to provide benefits during the Initial Coverage Period or any cash payment thereafter shall terminate at such time that the Executive commences employment with another employer and becomes eligible to receive medical insurance coverage under an employer-provided plan that is generally comparable to the Date of Termination Coverage, in which case the Executive shall rebate to SBH any unearned portion of the lump sum payment for the Extended Coverage Period.  The coverage provided hereunder shall be applied toward the satisfaction of, and shall not supplement, the Executive’s right to continued coverage under the Consolidated Omnibus Budget Reconciliation Act of 1985, as amended, or any similar state law. Notwithstanding the foregoing: (i) during the period of coverage, the benefits provided in

8

any one calendar year shall not affect the amount of benefits provided in any other calendar year (other than any life-time coverage limits under the applicable medical plans); (ii) the reimbursement of an eligible expense shall be made on or before December 31 of the year following the year in which the expense was incurred; and (iii) the Executive’s rights pursuant to this paragraph shall not be subject to liquidation or exchange for another benefit.

Executive Outplacement. SBH will pay for and provide to the Executive outplacement services with an outplacement firm of Executive’s choosing, provided that SBH shall not be responsible to pay for such services to the extent such services (i) exceed $12,000 or (ii) are provided more than one year following the Date of Termination.

9