AMENDED CLASS ACTION SETTLEMENT AGREEMENT

EXHIBIT 10.5.1

IN THE UNITED STATES DISTRICT COURT

FOR THE NORTHERN DISTRICT OF ALABAMA

AMENDED CLASS ACTION SETTLEMENT AGREEMENT

This AMENDED CLASS ACTION SETTLEMENT AGREEMENT is entered into by and among Settlement Class Representatives for themselves and on behalf of the Settlement Class, the Settling Defendants and the Underwriters. Italicized and capitalized terms and phrases have the meanings provided in Section 1 below.

RECITALS

WHEREAS, Settlement Class Representatives have commenced actions comprising the ERISA Action asserting various Claims for relief against the Named Settling Defendants, all of which Claims are disputed by the Settling Defendants;

WHEREAS, a dispute exists with respect to the existence and/or extent of insurance coverage available or exclusions or policy defenses applicable to certain Defendants under the Insurance Policies;

WHEREAS, the parties have engaged in mediation before the Mediator to explore settlement possibilities, and the Mediator has conducted a series of mediation sessions in which the Settling Parties have participated;

WHEREAS, the Settling Parties are desirous of promptly and fully resolving and settling with finality all of the Released Claims asserted by Settlement Class Representatives, for themselves and on behalf of the Settlement Class, against the Settling Defendants, and the Settling Defendants and Underwriters are desirous of promptly and fully resolving and settling with finality any Claims against each other relating to the Insurance Policies;

WHEREAS, on June 3, 2005, the Settlement Class Representatives, the Underwriters, and the Settling Defendants (with the exceptions of Messrs. Scrushy, Martin, Owens, and Beam) executed a term sheet setting forth their settlement agreement in principle, and pursuant thereto, on June 17, 2005, the Company and the Underwriters deposited the Settlement Amount into the Settlement Fund;

WHEREAS, the Court issued an Order on August 22, 2005 in which it encouraged the parties to reach a global settlement to which Messrs. Scrushy, Martin, Owens, and Beam would be parties;

WHEREAS, pursuant to the Court’s August 22, 2005 Order, the Settling Parties resumed negotiations and have reached a settlement by and through their respective counsel on the terms and conditions set forth in this Amended Settlement Agreement;

NOW, THEREFORE, the Settling Parties, in consideration of the promises, covenants and agreements herein described and for other good and valuable consideration acknowledged by each of them to be satisfactory and adequate, and intending to be legally bound, do hereby mutually agree as follows:

1. As used in this Amended Settlement Agreement, italicized and capitalized terms and phrases not otherwise defined have the meanings provided below:

1.1 “Affiliate” shall mean: any entity which owns or controls, is owned or controlled by, or is under common ownership or control with, a Person. For purposes of this definition, “control” shall mean the possession, directly or indirectly, of the power to direct or cause the direction of the management and policies of such Person, whether through the ownership of voting securities or otherwise.

1.2 “Agreement Execution Date” shall mean: the date on which this Amended Settlement Agreement is fully executed, as provided in Section 20.13 below.

1.3 “Approval Order” shall have the meaning set forth in Section 2.2.

1.4 “Bar Order” shall have the meaning set forth in Section 2.2 below.

1.5 “Bar Order Notice” shall mean: the form of notice appended as Exhibit C to the form of Preliminary Approval Order attached hereto as Exhibit 1.

1.6 “Barred Persons” shall have the meaning set forth in Section 9.1.

2

1.7 “Claims” shall mean: any and all claims of any nature whatsoever (including claims for any and all losses, damages, unjust enrichment, attorneys’ fees, disgorgement of fees, litigation costs, injunction, declaration, contribution, indemnification or any other type or nature of legal or equitable relief), whether accrued or not, whether already acquired or acquired in the future, whether known or unknown, in law or equity, brought by way of demand, complaint, cross-claim, counterclaim, third-party claim or otherwise.

1.8 “Class Exemption” shall mean: Prohibited Transaction Exemption 2003-39, “Release of Claims and Extensions of Credit in Connection with Litigation” issued December 31, 2003, by the United States Department of Labor, 68 Fed. Reg. 75,632.

1.9 “Class Notice” shall mean: the form of notice appended as Exhibit A to the form of Preliminary Approval Order attached hereto as Exhibit 1.

1.10 “Class Period” shall mean: the period from January 1, 1996 to the date of the Fairness Hearing.

1.11 The “Company” shall mean: HEALTHSOUTH Corporation, a Delaware corporation, each of its Affiliates, as well as each of its predecessors and Successors-In-Interest.

1.12 The “Court” shall mean: the United States District Court for the Northern District of Alabama.

1.13 “Custodian” shall mean: Wells Fargo Bank, N.A., as custodian of the Settlement Fund .

1.14 “Derivative Actions” shall mean all derivative actions filed by shareholder plaintiffs in the name of the Company, including but not limited to Tucker v. Scrushy, No. CV-02-5212 (Ala. Cir. Ct.).

1.15 “DOL ” shall mean: the United States Department of Labor.

1.16 “ERISA” shall mean: the Employee Retirement Income Security Act of 1974, as amended, including all regulations promulgated and case law thereunder.

1.17 “ERISA Action” shall mean: In re HealthSouth Corp. ERISA Litigation, CV-03-BE-1700, a consolidated action pending in the Court, and any and all cases now or hereafter consolidated therewith.

1.18 “Fairness Hearing” shall have the meaning set forth in Section 2.2.

1.19 “Final” shall mean: with respect to the Approval Order, that such order shall have been entered by the Court and the time for appeal or writ of certiorari shall have expired without the initiation of an appeal or petition for writ of certiorari, or, if an appeal or petition for writ of certiorari has been timely initiated, that there has occurred a full and final disposition of any such appeal or writ of certiorari without a reversal or modification, including the exhaustion of proceedings in any remand and/or subsequent appeal after remand. Notwithstanding any other provision hereof, the Approval Order shall be deemed Final regardless of whether the Court has entered an order regarding the Plan of Allocation or the award of legal fees and expenses and regardless of whether any such order, if entered, has become Final.

3

1.20 “Independent Fiduciary” shall mean: a Plan fiduciary retained at the Company’s expense that has no “relationship to” or “interest in” (as those terms are used in the Class Exemption) any of the Settling Parties.

1.21 “Insurance Policies” shall mean: (a) Federal Insurance Company Excess Policies Nos. 5152-84-82 and 8152-84-82A-BHM; and (b) Travelers Casualty & Surety Company of America Policy No. 076 FF 103027063 BCM.

1.22 “Judgment Reduction Amount” shall have the meaning set forth in Section 10.

1.23 “Lead Counsel” shall mean: Keller Rohrback, L.L.P., as lead counsel for the Settlement Class Representatives in the ERISA Action.

1.24 “Mediator” shall mean: Eric Green.

1.25 “Named Settling Defendants” shall mean: the Company, Brandon Hale, Dennis Wade, Kimberly McCracken, Marca Pearson, Barbara Roper, Philip Watkins, James P. Bennett, P. Daryl Brown, John S. Chamberlin, Larry D. Striplin, Jr., Charles W. Newhall, III, George H. Strong, Richard F. Celeste, C. Sage Givens, Joel C. Gordon, Larry R. House, Anthony J. Tanner, Raymond J. Dunn, III, Allan R. Goldstein, Robert P. May, Jan L. Jones, Jon F. Hanson, Lee S. Hillman, Richard M. Scrushy, Aaron Beam, Jr., William T. Owens, and Michael D. Martin.

1.26 “Net Settlement Amount” shall have the meaning set forth in Section 5.

1.27 This paragraph is hereby deleted.

1.28 “Person” shall mean: an individual, partnership, corporation, governmental entity or any other form of entity or organization.

1.29 “Plan” shall mean: the HealthSouth Corporation Employee Stock Benefit Plan, including all amendments thereto in effect at any point between January 1, 1991 and the present.

1.30 “Plan of Allocation” shall mean: the plan of allocation approved by the Court as contemplated by Section 13.

1.31 “Preliminary Approval Order” shall have the meaning set forth in Section 2.

1.32 “Preliminary Motion” shall have the meaning set forth in Section 2.

1.33 “Released Claims” shall have the meaning set forth in Section 7.

1.34 “Releasees” shall mean: the Settling Defendants, the Plan, the Underwriters, and the present and former Representatives of each of them.

1.35 “Representatives” shall mean: representatives, attorneys, agents, directors, officers, employees, insurers and reinsurers.

4

1.36 “RICO” shall mean: the Racketeer Influenced and Corrupt Organizations Act of 1970, as amended, including all regulations promulgated and case law thereunder.

1.37 “Securities Actions” shall mean: all securities actions pertaining to the Company, including but not limited to the action proceeding as a consolidated class action captioned In re HealthSouth Corp. Securities Litig., No. CV-03-BE-1500-S (N.D. Ala.), and all actions that are or will be consolidated therein.

1.38 “Settlement” shall mean: the settlement to be consummated under the Amended Settlement Agreement pursuant to the Amended Approval Order.

1.39 “Amended Settlement Agreement” shall mean this Amended Class Action Settlement Agreement.

1.40 “Settlement Amount” shall mean: $25,000,000.

1.40.1 “Supplemental Settlement Amount” shall mean: $4,500,000, to be paid to resolve all Released Claims in this case against Defendant Richard M. Scrushy. Payment shall be made as follows:

1.40.1.1 Defendant Scrushy will pay $1,500,000 within six (6) months of Preliminary approval of the Settlement, or 30 days after the Approval Order becomes Final, whichever is later.

1.40.1.2 In addition to the amounts already provided in connection with the Settlement Agreement executed in July 2005, the Underwriters shall pay $2,000,000 to the Settlement Fund within twenty (20) business days of execution of the Amended Settlement Agreement by each of the Settling Parties.

1.40.1.3 In addition to the amounts already provided in connection with the Settlement Agreement executed in July 2005, in the event that the Company recovers all or any portion of the judgment entered on January 3, 2006 against Defendant Scrushy in the HealthSouth Corporation 2002 Derivative Litigation (CV 02-5212) (the “Bonus Judgment” ), the Company shall pay the first $1,000,000 collected from the Bonus Judgment, net of plaintiff’s attorney’s fees, to the Settlement Fund in a manner that is approved by the Court (such that a total of $1,000,000 is contributed to the Supplemental Settlement Amount ). If the Company fails to collect any of the Bonus Judgment, the Company shall have no obligation to pay any of the Supplemental Settlement Amount and the Supplemental Settlement Amount shall be reduced to $3,500,000.

1.40.2 “Martin Supplemental Settlement Amount” shall mean: $350,000, to be paid by Defendant Michael D. Martin to resolve all Released Claims in this case against Defendant Martin. Payment shall be made within ten (10) days of the execution of the Amended Settlement Agreement.

5

1.40.3 “Combined Settlement Amount” shall mean the combination of the Settlement Amount, the Supplemental Settlement Amount, and the Martin Supplemental Settlement Amount.

1.41 “Settlement Class” shall have the meaning set forth in Section 12.

1.42 “Settlement Class Representatives” shall mean: the following Persons, as plaintiffs on behalf of themselves and on behalf of all members of the Settlement Class: Kim Coggins, Kim French, and Robert J. Lancaster and each of their Successors-In-Interest. Settlement Class Representatives intend that all rights and obligations that are binding on Settlement Class Representatives under this Amended Settlement Agreement, including each and every covenant, agreement, and warranty, also shall be binding on all members of the Settlement Class.

1.43 “Settlement Fund” shall mean: an account established by Lead Counsel at Wells Fargo Bank, N.A., denominated HealthSouth ERISA Litigation Settlement Fund.

1.44 “Settling Defendants” shall mean: the Named Settling Defendants, each of their respective Affiliates, predecessors, and Successors-in-Interest, and any directors, officers or employees of the Company.

1.45 “Settling Defendant’s Counsel” or “Underwriter’s Counsel” shall mean, for each Settling Defendant or Underwriter, as the case may be, the counsel identified as such Settling Defendant’s or Underwriter’s counsel in Section 20.9.

1.46 “Settling Parties” shall mean: the Settlement Class Representatives, the Settling Defendants, and the Underwriters.

1.47 “Successor-In-Interest” shall mean: a Person’s estate, legal representatives, heirs, successors or assigns.

1.47 “Underwriters” shall mean: Travelers Casualty & Surety Company of America and Federal Insurance Company and each of their respective Affiliates, predecessors, and Successors-In-Interest.

2. As soon as practicable following the complete execution of this Amended Settlement Agreement by all Settling Parties, Settlement Class Representatives will file a motion (“Preliminary Motion”) with the Court for an order substantially in the form annexed hereto as Exhibit 1, including the exhibits thereto (the “Preliminary Approval Order”). The Settlement Class Representatives and the Settling Defendants shall request that a preliminary hearing to consider the compromise and settlement before the Court be held as soon as practicable thereafter.

2.1 On the date and in the manner set by the Court in its Preliminary Approval Order, the Settlement Class Representatives shall cause the Class Notice and the Bar Order Notice to be (a) transmitted in the form and manner approved by the Court to the Persons as directed by the Court in the Preliminary Approval Order, and (b) published as directed by the Court in the Preliminary Approval Order. Costs associated with the publication and service of notice,

6

establishment of the Settlement Fund, and tax payments relating to the Settlement Fund shall be paid from the Combined Settlement Amount. Lead Counsel agrees to be responsible for arranging publication and distribution of the Class Notice and Bar Order Notice to the proposed Settlement Class and other Persons as required by the Preliminary Approval Order. The Settling Defendants and the Underwriters shall have no responsibility for providing publication or distribution of the Settlement or the notice of the Settlement to the Settlement Class, but Settling Defendants reserve the right to approve the contents of the Class Notice and the Bar Order Notice. The Settlement Class Representatives and the Settling Defendants shall request that a hearing before the Court to consider final approval of the Settlement be held as soon as possible following preliminary approval and due and proper notice being served or published.

2.2 On or after the date set by the Court for the hearing to consider final approval of the Settlement (the “Fairness Hearing”) the Settlement Class Representatives and the Settling Defendants shall request that the Court determine: (i) whether to enter judgment finally approving the Settlement and entering a bar order satisfying all of the terms of Section 9 below (the “Bar Order”), all substantially in the form attached hereto as Exhibit 2 (which judgment is referred to herein as the “Approval Order”); (ii) whether the distribution of the Combined Settlement Amount as provided in the Plan of Allocation should be approved; and (iii) what legal fees, compensation and further expenses should be awarded or reserved for award to Lead Counsel and other counsel for Settlement Class Representatives as contemplated by Section 4 of this Amended Settlement Agreement.

3. Settlement Class Representatives, on behalf of the Settlement Class and the Plan, agree to settle and fully resolve the Claims asserted in the ERISA Action against all Settling Defendants (except Defendants Richard M. Scrushy and Michael D. Martin) for the Settlement Amount, against Defendant Scrushy for the Supplemental Settlement Amount, and against Defendant Martin for the Martin Supplemental Settlement Amount, as set forth below.

3.1 In consideration of all the promises and agreements set forth in the Amended Settlement Agreement, Defendants Scrushy and Martin, the Underwriters, and the Company shall have caused their respective portions of the Settlement Amount, Supplemental Settlement Amount, and Martin Supplemental Settlement Amount to be deposited into the Settlement Fund in the manner set forth in the Amended Settlement Agreement; except that the Company’s obligation to contribute $1,000,000 from the Bonus Judgment is subject to the conditions set forth in section 1.40.1.3. Interest earned on the Combined Settlement Amount shall be applied to the expenses of settlement administration, if any, or otherwise shall accrue for the benefit of the Settlement Class. The Settlement Fund shall be invested only in United States Treasury securities, and/or securities issued by government entities backed by the full faith and credit

7

of the United States Treasury, and/or securities of United States Government Sponsored Enterprises that carry a rating of Aaa, and money market mutual funds that invest exclusively in the foregoing securities.

3.2 The Settlement Fund shall be structured and managed to qualify as a Qualified Settlement Fund under Section 468B of the Internal Revenue Code and Treasury regulations promulgated thereunder and shall make tax filings and provide reports to Lead Counsel for tax purposes. The Settling Parties shall not take a position in any filing or before any tax authority inconsistent with such treatment.

3.3 The Settlement Amount, Supplemental Settlement Amount, and Martin Supplemental Settlement Amount shall be the full and sole monetary payments made by or on behalf of the Settling Defendants and the Underwriters to the Settlement Class in connection with the Settlement.

4. Upon the entry by the Court of the Approval Order and an order granting Lead Counsel’s request for attorneys’ fees and costs as contemplated by Section 2.2(iii), Lead Counsel shall be entitled to withdraw from the Settlement Fund attorneys’ fees and costs as approved by the Court based on the common fund doctrine. Settling Defendants shall take no position with respect to the amount of the costs or attorneys’ fees sought by Lead Counsel in this matter, and shall leave the amount to the sound discretion of the Court. Upon the entry by the Court of the Approval Order, the three Settlement Class Representatives may apply to the Court for compensation in an amount not to exceed five thousand dollars ($5,000) for each of the three Settlement Class Representatives, payable solely from the Settlement Fund to the extent awarded by the Court. The Court’s consideration of Lead Counsel’s request for attorneys’ fees and costs and the Settlement Class Representatives’ application for compensation are matters separate and apart from the Settlement between the Settling Parties, and no decision by the Court concerning the Lead Counsel’s attorneys’ fees and costs or the Settlement Class Representatives’ compensation shall affect the validity of the Amended Settlement Agreement or finality of the Settlement in any manner.

5. The Combined Settlement Amount plus interest earned, less costs of administration pursuant to Section 2.1, Lead Counsel’s reasonable expenses, costs, and attorneys’ fees, and Settlement Class Representatives’ compensation as approved by the Court (“Net Settlement Amount”), shall be released from escrow and paid to the Plan, subject to the procedures set forth in Section 6, upon written notification to the Custodian that the Approval Order is Final. The Net Settlement Amount will be paid to the Plan in order to preserve to the fullest extent possible its tax protected status under ERISA.

5.1 Within 180 days after the Approval Order becomes Final, the Company shall take any action that it deems necessary or appropriate, as determined in its sole discretion, including but not limited to amending,

8

terminating, or in any way changing the Plan, with the intent that the Net Settlement Amount is not invested or paid from the Plan as benefits in the form of the Company’s common stock, and is not invested in cash except as necessary to administer the Plan. Such amendments or changes may include, but are not limited to, any amendments or changes to the Plan that permit all or a portion of the Net Settlement Amount allocated to Class members who are then current participants in the HealthSouth Retirement Investment Plan to be invested by them in the same or similar investment options available under the HealthSouth Retirement Investment Plan or successors thereto.

6. In the event the Approval Order is not approved by the Court or does not become Final, the Settling Parties shall negotiate in good faith in order to modify the terms of the Amended Settlement Agreement in order to revive the Settlement. In the event that such efforts are not successful:

(i) the Combined Settlement Amount, plus any interest at the rate of the escrow account, minus the amount already reasonably applied to costs of Settlement as permitted in Section 2.1, shall be immediately returned to the Company, Scrushy, Martin, and the Underwriters in proportion to the parties’ contributions thereto, less a reserve sufficient to meet the income tax liability of the Settlement Fund with respect to its earnings, with Lead Counsel being jointly and severally liable for any failure to return this amount;

(ii) the Settling Defendants will not be deemed to have consented to the certification of any class, and the agreements and stipulations in this Amended Settlement Agreement concerning class definition or class certification shall not be used as evidence or argument to support class certification or class definition, and the Settling Defendants will retain all rights to oppose class certification, including certification of a class identical to that provided for in this Amended Settlement Agreement for any other purpose; and

(iii) the Settlement and this Amended Settlement Agreement, including but not limited to the releases and orders therein, shall become null and void and of no further force and effect, the parties shall be deemed to have reverted to their respective status and positions as of the date immediately before the date of the execution hereof, and the parties shall proceed in all respects as if this Amended Settlement Agreement had not been executed.

7. Upon the entry of the Approval Order by the Court, Settlement Class Representatives, on behalf of the Settlement Class and the Plan, will absolutely and unconditionally release and discharge the Releasees from:

(i) any and all ERISA-based and RlCO-based Claims related to the acquisition, disposition, or retention of stock by the Plan and/or its fiduciaries during the Class Period;

9

(ii) any and all Claims related to the appointment, removal, or monitoring of any fiduciary for the Plan;

(iii) any and all Claims related to the preparation or dissemination, directly or indirectly, to Plan participants and beneficiaries of information relating to Company stock;

(iv) any and all Claims related to the Insurance Policies;

(v) any and all ERISA- based Claims asserted, or that could have been asserted, in the ERISA Action and ERISA- based Claims, known or unknown, arising from or related to the acts, omissions, facts or events alleged in the ERISA Action;

(vi) any and all Claims in connection with, based upon, arising out of, or relating to the Settlement, but excluding Claims to enforce the terms of the Settlement; and

(vii) any and all Claims based upon, arising out of, or relating to any Person ’s liability to the Settlement Class or the Plan for Claims set forth in any of the preceding subsections (i) through (vi),

and any fees, costs, judgments, and/or settlement amounts arising out of such Claims. The Claims described above in subparagraphs (i)-(vii) shall be referred to collectively as the Rel