EMPLOYMENT AGREEMENT

EXHIBIT 10.18.1

EMPLOYMENT AGREEMENT

This Employment Agreement (the “Agreement”), made and entered into as of February 1, 2004 (the “Effective Date”), is by and between HEALTHSOUTH CORPORATION, a Delaware corporation (“Corporation”), and JOHN MARKUS, an individual resident of Connecticut (the “Executive”).

RECITALS

The Corporation desires to employ the Executive as its Senior Vice President and Chief Compliance Officer effective as of the Effective Date, and the Executive desires to accept such employment effective as of the Effective Date, on the terms and conditions set forth herein.

AGREEMENT

The parties, intending to be legally bound, agree as follows:

Section 1. Employment. The Corporation hereby employs the Executive, and the Executive hereby accepts employment, all on the terms and conditions herein.

Section 2. Services; Extent of Services.

(a) Duties and Responsibilities. The Executive is hereby employed as the Senior Vice President and Chief Compliance Officer of the Corporation, the authority, duties and responsibilities of which will be as follows: the Executive will (i) manage, review and supervise the regulatory compliance program, the internal audit program and the government relations function of the Corporation; (ii) report to Robert P. May, the Interim Chief Executive Officer of the Corporation, until such time that a permanent Chief Executive Officer of the Corporation is appointed and following such time that a permanent Chief Executive Officer of the Corporation is appointed, report to such Chief Executive Officer; (iii) have the powers and duties determined or directed by the Compliance Committee of the Board of Directors and the Chief Executive Officer of the Corporation; and (iv) comply with the various policies, procedures and codes of conduct of the Corporation in effect from time to time which apply to other employees and executive officers.

(b) Full Business Attention. The Executive will devote his full business attention and energies to the business of the Corporation during the Term (as defined below) and will physically report and will render all the Executive’s services contemplated hereunder to the Corporation at its offices in Birmingham, Alabama or at any other location in which the Corporation is headquartered; provided, however, that the foregoing requirement to render services in Birmingham shall not apply when the Executive is traveling on company business.

1 of 14

(c) Other Activities. Notwithstanding anything to the contrary contained in Section 2(b), the Executive will be permitted to engage in the following activities, provided that such activities do not materially interfere or conflict with the Executive’s duties and responsibilities to the Corporation;

(i) the Executive may serve on the governing boards of, or otherwise participate in, a reasonable number of trade associations and charitable organizations whose purposes are not inconsistent with the activities and the image of the Corporation;

(ii) the Executive may engage in a reasonable amount of charitable activities and community affairs; and

(iii) subject to the prior approval of the Nominating / Corporate Governance Committee of the Board of Directors of the Corporation, the Executive may serve on the board of directors of up to one business corporations or other for-profit entities, provided that they do not compete, directly or indirectly, with the Corporation.

Section 3. Compensation.

(a) Base Salary. In consideration of the services provided hereunder, the Corporation shall pay the Executive during the Term a salary of $363,000 per year (the “Base Salary”). The Corporation shall pay the Base Salary in arrears in equal installments in accordance with the Corporation’s payroll policy in effect from time to time for other senior executives of the Corporation.

(b) Bonus. Within thirty (30) days of the Effective Date, Executive shall receive a signing bonus of $70,000. During the Term, the Executive will be entitled to receive cash bonus payments in an amount per year targeted at 60% of the amount of the Base Salary in accordance with the senior management bonus plan, which is currently being developed.

(c) Benefits. During the Term, the Executive will be entitled to the following benefits:

(i) Employee Benefit Plans. The Executive will be entitled to participate in all employee benefit plans of the Corporation (including incentive or equity compensation plans) on such terms as are offered for the general benefit of other senior executive officers of the Corporation, subject to the provisions of such plans as may be in effect from time to time.

2 of 14

(ii) Vacation; Sick Leave. The Executive will be entitled to vacation and sick leave on such terms as are offered for the benefit of other senior executives of the Corporation.

(d) Expense Reimbursement. The Corporation shall reimburse the Executive, in accordance with the Corporation’s policies, for all reasonable business expenses incurred by the Executive in connection with the performance of the Executive’s obligations hereunder.

(e) Taxes. All payments made by the Corporation under this Agreement will be subject to withholding of such amounts as is required pursuant to any applicable law or regulation.

(f) Equity Incentives. The Corporation agrees to provide the Executive with equity incentives commensurate with the Executive’s position and responsibilities with the Corporation.

(g) Relocation Expenses. The Corporation shall reimburse the Executive for the following expenses (to the extent they are reasonable and documented) incurred by the Executive in connection with relocating his family to a new primary residence in Birmingham, Alabama or surrounding communities:

(i) house hunting trips for the purpose of searching for a new primary residence;

(ii) temporary living expenses;

(iii) transportation of household goods and vehicles to a new primary residence;

(iv) closing costs incurred in connection with the purchase of the primary residence in Birmingham, Alabama; and

(v) closing costs, including real estate agency commissions relating to the sale of the Executive’s primary residence in Connecticut

Section 4. Term. The term of this Agreement will commence on the Effective Date and will continue for a term of three (3) years following the term (the “Term”), unless earlier terminated pursuant to the provisions of Section 5 below.

Section 5. Termination of Employment.

(a) Termination by Corporation for Cause. The Executive’s employment by the Corporation will terminate immediately upon written notice

3 of 14

to the Executive if the Corporation elects to discharge the Executive for Cause. For purposes hereof, “Cause” means:

(i) the Executive’s act of fraud, misappropriation, or embezzlement with respect to the Corporation;

(ii) the Executive’s indictment for, conviction of, or plea of guilt or no contest to, any felony;

(iii) the suspension or debarment of the Executive or of the Corporation or any of its affiliated companies or entities as a result of any act or omission of the Executive in connection with his employment with the Corporation from participation in any federal or state health care program;

(iv) the Executive’s admission of liability of, or finding of liability for, the violation of any “Securities Laws.” As used herein, the term “Securities Laws” means any federal or state law, rule or regulation governing the issuance or exchange of securities, including without limitation the Securities Act of 1933, the Securities Exchange Act of 1934 and the rules and regulations promulgated thereunder; or

(v) a determination by any agency or instrumentality of any state or the United States of America, including but not limited to the United States Department of Justice, the United States Securities and Exchange Commission or any committee of the United States Congress that the Executive’s employment impairs or impedes the ability of such agency or instrumentality to conduct investigations, and/or prosecute proceedings, into the actions or in-actions of any current or former employee of the Corporation (collectively, the “Investigations”);

(vi) the Executive’s failure after reasonable prior written notice to comply with any valid and legal directive of the Chief Executive Officer or the Board of Directors of the Corporation; or

(vii) Other than as provided in 5(a)(i) – (vi) above, the Executive’s material breach of any provision of this Agreement that is not remedied within fifteen (15) days of the Executive being provided written notice thereof from the Corporation.

Repeated breaches of a similar nature, such as the failure to report to work, perform duties, or follow directions, all as provided herein, shall not require additional notices as provided Section 5(a)(vi) or (vii).

4 of 14

(b) Termination by Corporation Without Cause. The Corporation may terminate this Agreement without Cause upon at least thirty (30) days prior written notice to the Executive.

(c) Death or Disability. The Executive’s employment by the Corporation will immediately terminate upon the Executive’s death and, at the option of either the Executive or the Corporation, exercisable upon written notice to the other party, may terminate upon the Executive’s Disability. For purposes of this Agreement, “Disability” will occur if (i) the Executive becomes eligible for full benefits under a long-term disability policy provided by the Corporation, if any, or (ii) the Executive has been unable, due to physical or mental illness or incapacity, to perform the essential duties of his employment with reasonable accommodation for a continuous period of ninety (90) days or an aggregate of one-hundred eighty (180) days during any consecutive 12-month period.

(d) Termination by the Executive for Good Reason. The Executive may terminate this Agreement at any time upon thirty (30) days’ written notice to the Corporation and the Corporation fails to cure such event within such thirty-day period (any such termination referenced in clauses (i)-(v) below, constituting termination for “Good Reason”):

(i) if the Corporation fails to make the payments or offer the benefits required by Section 3 hereof within thirty (30) days after any such payments or benefits are due;

(ii) if the Executive’s duties, authority or responsibilities as Chief Compliance Officer are substantially diminished so that they are no longer consistent with the position of a chief compliance officer of a public corporation, regardless of whether such diminution of duties is accompanied by a change in the Executive’s title;

(iii) except as otherwise set forth in clauses (i) and (ii) above, if the Corporation materially breaches any of its other duties hereunder.

(e) Termination by the Executive without Good Reason. The Executive may terminate this Agreement without Good Reason upon at least thirty (30) days prior written notice to the Corporation.

(f) Change in Control. The Executive may terminate this Agreement within sixty (60) days following a “Change in Control.” For purposes of this Agreement, a “Change in Control” will be deemed to have taken place if, whether in a single transaction or a series of transactions:

(i) any person or entity, including a “group” as defined in Section 13(d)(3) of the Securities Exchange Act of 1934, as amended, other than the Corporation, or any employee benefit plan of the

5 of 14

Corporation or any of its subsidiaries, becomes the beneficial owner of Corporation securities having 50% or more of the combined voting power of the then outstanding securities of the Corporation that may be cast for the election of directors of the Corporation (other than as a result of the issuance of securities initiated by the Corporation in the ordinary course of business);

(ii) as the result of, or in connection with, any cash tender or exchange offer, merger or other business combination, or any combination of the foregoing transactions, the holders of all the Corporation’s securities entitled to vote generally in the election of directors of the Corporation immediately prior to such transaction constitute, following such transaction, less than a majority of the combined voting power of the then-outstanding securities of the surviving entity (or in the event each entity survives, the surviving entity that is the parent entity) entitled to vote generally in the election of the directors of such surviving entity (or in the event each entity survives, the surviving entity that is the parent entity) after such transactions; or

(iii) the Corporation sells, transfers or leases all or substantially all of the assets of the Corporation and its subsidiaries, collectively.

Notwithstanding the foregoing, the occurrence of any of the following events, by themselves, will not be deemed to constitute a “Change in Control”: if, pursuant to or within the meaning of the United States Bankruptcy Code or any other federal or state law relating to insolvency or relief of debtors, the Corporation (A) commences a voluntary case or proceeding; or (B) consents to the entry of an order for relief against it in an involuntary case.

Section 6. Effect of Termination.

(a) Termination by the Corporation for Cause; Termination by the Executive Without Good Reason. Upon termination of this Agreement (i) by the Corporation for Cause pursuant to Section 5(a) above, or (ii) by the Executive without Good Reason pursuant to Section 5(e) above, the Executive will be entitled to receive (i) base salary and bonus payments, payments in respect of accrued but unpaid vacation and reimbursement for business expenses, in each case due, accrued or payable as of the date of such termination, and (ii) such vested stock options and other benefits as the Executive may be entitled to receive under any stock option or other employee benefit plan, but will not be entitled to receive the Severance Payment (as defined in Section 6(c) below).

(b) Other Termination. Upon termination of this Agreement (i) by the Corporation without Cause pursuant to Section 5(b) above (including termination without Cause following a Change in Control), (ii) by the Executive within sixty (60) days following a Change in Control pursuant to Section 5(f), (iii) by the

6 of 14

Corporation or the Executive as the result of the death or Disability of the Executive pursuant to Section 5(c) above, or (iv) by the Executive for Good Reason pursuant to Section 5(d) above, the Executive will be entitled to receive (1) base salary and any outstanding bonus payments entitlement to include payments in respect of accrued but unpaid vacation and reimbursement for business expenses, in each case due, accrued or payable as of the date of such termination), (2) such vested stock options and other benefits as Executive may be entitled to receive under any equity incentive plan or any other stock option or other employee benefit plan, and (3) the Severance Payment (as determined pursuant to Section 6(c) below), which Severance Payment will be payable in full by the Corporation within fifteen (15) business days of the date of such termination.

(c) Severance Payment. For purposes of this Agreement, “Severance Payment” means:

(i) in the event of any termination by the Corporation without Cause pursuant to Section 5(b) above (including termination without Cause following a Change in Control), an amount equal to the Executive’s Base Salary for the number of months remaining in the Term at the date of termination;

(ii) in the event of any termination by the Executive for Good Reason pursuant to Section 5(d), or in the event of a termination by Executive within sixty (60) days following a Change in Control, an amount equal to the Executive’s Base Salary for the number of months remaining in the Term at the date of termination;

(iii) in the event of any termination by the Corporation or the Executive as the result of the death or Disability of the Executive pursuant to Section 5(c) above, an amount equal to the Executive’s Base Salary for a period of three (3) full months.

Notwithstanding any provision of this Agreement to the contrary, the Severance Payment is subject to forfeiture for violations of Sections 8 or 9 of this Agreement. The amount of Severance Payment to be forfeited shall be prorated based upon the date of the violation.

(d) Consulting Contract. In the event that the contract expires without renewal, the Executive shall receive a one (1) year contract to furnish consulting services to the Company in connection with the areas of responsibility listed in paragraph 2 (a) of this Agreement with compensation equal to the Executive’s salary at the conclusion of the Term. Such period shall not be considered part of the Term of this Agreement and during this period the Executive shall not be eligible to receive any other payments or benefits apart from any bonus payments or other incentive awards earned during the final year of the Term and in

7 of 14

accordance with the plan design rules governing payout terms. Each party will have the right to terminate the “consulting contract” term with 90 days notice, however, no early termination payments, penalty payments or fees shall be paid upon termination. Upon termination, the Executive shall only be entitled to be paid any accrued but unpaid consulting fees and any bonus payments or other incentive awards earned during the final year of the Term that remain unpaid as of the termination date.

Section 7. Miscellaneous.

(a) Notices. All notices, consents, waivers, and other communications under this Agreement must be in writing and will be deemed to have been duly given when (i) delivered by hand (with written confirmation of receipt), (ii) sent by facsimile with confirmation of transmission by the transmitting equipment, (iii) received by the addressee, if sent by certified mail, return receipt requested, or (iv) received by the addressee, if sent by a nationally recognized overnight delivery service, return receipt requested, in each case to the appropriate addresses, or facsimile numbers set forth below (or to such other addresses, or facsimile numbers as a party may designate by notice to the other parties):

(b) Power and Authority. Each party warrants and represents that it has full power and authority to enter into and perform this Agreement, and the person signing this Agreement on behalf of such party has been properly authorized and empowered to enter into this Agreement.

(c) Remedies. The rights and remedies of the parties to this Agreement are cumulative and not alternative.

8 of 14

(d) Waiver. No failure to exercise, and no delay in exercising, on the part of either party, any privilege, any power or any right hereunder will operate as a waiver thereof, nor will any single or partial exercise of any privilege, right or power hereunder preclude further exercise of any other privilege, right or power hereunder.

(e) Entire Agreement and Modification. This Agreement constitutes the entire agreement between the parties with respect to the subject matter of this Agreement and supersedes all prior agreements, whether written or oral, between the parties with respect to its subject matter and constitutes a complete and exclusive statement of the terms of the agreement between the parties with respect to its subject matter. This Agreement may not be amended except by a written agreement signed by the party to be charged with the amendment.

(f) Assignment. This Agreement may not be assigned by any party hereto without the prior written consent of the non-assigning party; provided, however, that the Corporation may assign this Agreement without the consent of the Executive in connection with any transaction which constitutes a Change of Control. Subject to the foregoing, this Agreement will be binding upon and shall inure to the benefit of (i) in the case of the Executive, his heirs, executors, administrators and legal representatives, and (ii) in the case of the Corporation, its permitted successors and assigns.

(g) Severability. If any provision of this Agreement is held invalid or unenforceable by any court of competent jurisdiction, the other provisions of this Agreement will remain in full force and effect. The parties further agree that if any provision contained herein is, to any extent, held invalid or unenforceable in any respect under the laws governing this Agreement, they shall take any actions necessary to render the remaining provisions of this Agreement valid and enforceable to the fullest extent permitted by law and, to the extent necessary, shall amend or otherwise modify this Agreement to replace any provision contained herein that is held invalid or unenforceable with a valid and enforceable provision giving effect to the intent of the parties.

(h) Section Headings, Construction. The headings of Sections in this Agreement are provided for convenience only and will not affect its construction or interpretation. All references to “Section” or “Sections” refer to the corresponding Section or Sections of this Agreement unless otherwise specified. All words used in this Agreement will be construed to be of such gender or number as the circumstances require. Unless otherwise expressly provided, the word “including” does not limit the preceding words or terms. The language used in the Agreement will be construed, in all cases, according to its fair meaning, and not for or against any party hereto. The parties acknowledge that each party has reviewed this Agreement and that rules of construction to the effect that any ambiguities are to be resolved against the drafting party will not be available in the interpretation of this Agreement.

9 of 14

(i) Governing Law. This Agreement will be governed by and construed in accordance with the laws of the State of Alabama, without regard to the conflict of law provisions thereof.

(j) Counterparts. This Agreement may be executed in one or more counterparts, each of which will be deemed to be an original copy of this Agreement and all of which, when taken together, will be deemed to constitute one and the same agreement.

(k) Attorneys’ Fees. The parties agree that in the event it becomes necessary to seek judicial remedies for the breach or threatened breach of this Agreement, the prevailing party will be entitled, in addition to all other remedies, to recover from the non-prevailing party all costs of such judicial action, including but not limited to, costs of investigation and defense and reasonable attorneys’ fees and expenses, and also including all such expenses related to any appeal.

(l) Further Assurances. Each party hereto shall perform such further acts and execute and deliver such further documents as may be reasonably necessary to carry out the provisions of this Agreement.

(m) No Third Party Beneficiary. This Agreement shall not confer any rights or remedies upon any person or entity other than the parties hereto and their respective successors and assigns.

Section 8. Non-Competition.

(a) The Executive acknowledges and recognizes the highly-competitive nature of the business conducted by the Corporation and its subsidiaries and affiliates and accordingly agrees that, in consideration of this Agreement and the premises contained herein, he shall not, for his own benefit or for the benefit of any other person or entity other than the Corporation, during the period commencing on the Effective Date hereof and terminating on the second anniversary of the expiration or termination of the Term hereof for any reason whatsoever (subject to Section 8(d)):

(i) contact, solicit or service any person or entity that was a customer or prospective customer of the Corporation or any of its subsidiaries or affiliates at any time during the Term hereof (a prospective customer being one to which the Corporation had made a written financial proposal within twelve (12) months prior to the time of the termination of the Term); or

(ii) hire, retain or engage as a director, officer, employee, consultant, agent or in any other capacity any person or persons who are

10 of 14

employed by the Corporation or who were at any time (within a period of six (6) months immediately prior to the date of the termination of the Term) employed by the Corporation or otherwise interfere with the relationship between such persons and the Corporation.

(b) The Executive understands that the foregoing restrictions may limit his ability to earn a similar amount of money in a business similar to the business of the Corporation or its subsidiaries or affiliates, but he nevertheless believes that he has received and will receive sufficient consideration and other benefits as an employee of the Corporation and as otherwise provided hereunder to clearly justify such restrictions which, in any event (given his education, skills and ability), the Executive does not believe would prevent him from earning a living.

(c) It is agreed that the Executive’s services hereunder are special, unique, unusual and extraordinary giving them peculiar value, the loss of which cannot be reasonably or adequately compensated for by damages, and in the event of the Executive’s breach of this Section, the Corporation shall be entitled to equitable relief by way of injunction or otherwise. If the period of time or area herein specified should be adjudged unreasonable in any court proceeding, then the period of time shall be reduced by such number of months or the area shall be reduced by elimination of such portion thereof as deemed unreasonable, so that this covenant may be enforced during such period of time and in such areas as is adjudged to be reasonable.

Section 9. Confidential Information.

(a) The Executive acknowledges that during the Term he will have access to and may obtain, develop, or learn of Confidential Information (as defined below).

(b) The Executive agrees that he shall hold such Confidential Information in strictest confidence and that the Executive shall not at any time, during or after the Term, in any manner, either directly or indirectly, use (for his own benefit or otherwise), divulge, disclose or communicate to any unauthorized person or entity in any manner whatsoever any Confidential Information.

(c) Under this Agreement, the term “Confidential Information” shall include, but not be limited to, any of the following information relating to the Corporation or its affiliates learned by the Executive during the Term or as a result of his employment with the Corporation:

(i) information regarding the Corporation’s business proposals, manner of the Corporation’s operations, and methods of selling or pricing any products or services;

11 of 14

(ii) the identity of persons or entities (including physicians and vendors) actually conducting or considering conducting business with the Corporation, and any information in any form relating to such persons or entities and their relationship or dealings with the Corporation or its affiliates;

(iii) any trade secret or confidential information of or concerning any business operation or business relationship;

(iv) computer databases, software programs and information relating to the nature of the hardware or software and how said hardware or software are used in combination or alone; and

(v) any other trade secret or information of a confidential or proprietary nature.

(d) During the Term, the Executive shall use, divulge, disclose or communicate Confidential Information only in the scope of his employment with the Corporation and only as expressly directed or permitted by the Corporation. The Executive shall not, at any time following the expiration or termination of this Agreement for any reason whatsoever, use, divulge, disclose or communicate for any purpose any Confidential Information. The Executive shall not make or use any notes or memoranda relating to any Confidential Information except for the benefit of the Corporation, and will, at the Corporation’s request, return each original and every copy of any and all notes, memoranda, correspondence, diagrams or other records, in written or other form, that he may at any time have within his possession or control that contain any Confidential Information.

(e) Except as provided for herein below, the Executive agrees that he will treat the terms of this Agreement as confidential, and shall not directly or indirectly disclose them in any manner except: (i) as mutually agreed upon in writing by the parties to this Agreement; (ii) in legal documents filed with the court or any arbitrator in any action to enforce the terms of this Agreement; (iii) pursuant to a valid order or regulation; (iv) as otherwise required by law or regulation; or (v) to his attorney, financial advisors, accountant, and/or spouse, provided that prior to any such disclosure, that individual must agree to treat as confidential all information disclosed.

(f) It is agreed that in the event of the Executive’s breach of this Section, the Corporation shall be entitled to equitable relief by way of injunction or otherwise.

(g) Notwithstanding the foregoing, Confidential Information shall not include information which has come within the public domain through no fault of or action by the Executive or which has become rightfully available to the Executive on a non-confidential basis from any third party, the disclosure of

12 of 14

which to the Executive does not violate any contractual or legal obligation such third party has to the Corporation or its affiliates with respect to such Confidential Information.

Section 10. Proprietary Developments.

(a) Any and all inventions, products, discoveries, improvements, processes, methods, computer software programs, models, techniques, or formulae (collectively, hereinafter referred to as “Developments”), made, developed, or created by the Executive (alone or in conjunction with others, during regular work hours or otherwise) during the Term, which may be directly or indirectly useful in, or relate to, the business conducted or to be conducted by the Corporation will be promptly disclosed by the Executive to the Corporation and shall be the Corporation’s exclusive property. The term “Developments” shall not be deemed to include inventions, products, discoveries, improvements, processes, methods, computer software programs, models, techniques, or formulae which were in the possession of the Executive prior to the Term. The Executive hereby transfers and assigns to the Corporation all proprietary rights which the Executive may have or acquire in any Developments and the Executive waives any other special right which the Executive may have or accrue therein. The Executive agrees to execute any documents and to take any actions that may be required, in the reasonable determination of the Corporation’s counsel, to effect and confirm such assignment, transfer and waiver.

(b) The Executive will execute any documents necessary or advisable, in the reasonable determination of the Corporation’s counsel, to direct the issuance of patents, trademarks, or copyrights to the Corporation with respect to such Developments as are to be the Corporation’s exclusive property or to vest in the Corporation title to such Developments; provided, however, that the expense of securing any patent, trademark or copyright shall be borne by the Corporation.

(c) The parties agree that Developments shall constitute Confidential Information.

[remainder of page intentionally left blank]

13 of 14

[signature page of Employment Agreement]

IN WITNESS WHEREOF, the undersigned parties have caused this Agreement to be executed by themselves or by their duly authorized representatives as of the day and date first written above.