EXHIBIT 5.1

[SKADDEN, ARPS, SLATE, MEAGHER & FLOM LETTERHEAD]

March 30, 2007

HealthSouth Corporation

One HealthSouth Parkway

Birmingham, Alabama 35243

Re: HealthSouth Corporation

Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as special counsel to HealthSouth Corporation, a Delaware corporation (the “Company”), and are delivering this opinion in connection with the preparation of a registration statement on Form S-8 of the Company (the “Registration Statement”) to be filed with the Securities and Exchange Commission (the “Commission”), on March 30, 2007, relating to the registration by the Company of 17,207,298 shares (the “Shares“) of the Company’s common stock, par value $0.01 per share (the “Common Stock”), authorized for issuance pursuant to the HealthSouth Corporation 2005 Equity Incentive Plan, HealthSouth Corporation 2004 Amended and Restated Director Incentive Plan, HealthSouth Corporation 2002 Non-Executive Stock Option Plan, HealthSouth Corporation 1999 Exchange Option Plan, HealthSouth Corporation 1998 Restricted Stock Plan, HealthSouth Corporation 1997 Stock Option Plan, HealthSouth Corporation 1995 Stock Option Plan, HealthSouth Corporation Amended and Restated 1993 Consultants Stock Option Plan and HealthSouth Corporation Key Executive Incentive Program (collectively, the “Plans” and each, individually, a “Plan”).

This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act of 1933, as amended (the “Securities Act”).

In rendering the opinion set forth herein, we have examined originals or copies, certified or otherwise identified to our satisfaction of the following: (i) the Plans; (ii) the Registration Statement in the form it is to be filed with the Commission on March 30, 2007; (iii) the Amended and Restated Certificate of Incorporation of the Company, as amended to the date hereof and currently in effect, certified by the Secretary of State of the State of Delaware; (iv) the Amended and Restated By-Laws of the Company, as amended to the date hereof and currently in effect, certified by the Secretary of the

HealthSouth Corporation

March 30, 2007

Page 2

Company; (v) a certificate, dated as of March 30, 2007, from the Secretary of State of the State of Delaware, as to the existence and good standing in the State of Delaware of the Company; (vi) certain resolutions of the Board of Directors of the Company relating to the Plans, the filing of the Registration Statement and certain related matters; (vii) a specimen certificate representing the Common Stock; and (viii) certain resolutions adopted by the stockholders of the Company. We also have examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Company and such agreements, certificates and receipts of public officials, certificates of officers or other representatives of the Company and others, and such other documents as we have deemed necessary or appropriate as a basis for the opinion set forth below.

In our examination, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as facsimile, electronic, certified or photostatic copies, and the authenticity of the originals of such copies. In making our examination of executed documents, we have assumed that the parties thereto, other than the Company, had the power, corporate or other, to enter into and perform all obligations thereunder and have also assumed the due authorization by all requisite action, corporate or other, and the execution and delivery by such parties of such documents and the validity and binding effect thereof on such parties. As to any facts material to the opinion expressed herein that we did not independently establish or verify, we have relied upon statements and representations of officers and other representatives of the Company and others and of public officials.

In rendering the opinion set forth below, we have assumed that the certificates evidencing the Shares in the form examined by us will be manually signed by an authorized officer of the transfer agent and registrar for the Common Stock and registered by such transfer agent and registrar. In rendering the opinion set forth below, we have also assumed that each agreement setting forth the terms of each grant of options or other awards under the Plans is or will be consistent with the applicable Plan and has been or will be duly authorized and validly executed and delivered by the parties thereto.

We do not express any opinion as to the laws of any jurisdiction other than the laws of the State of Delaware.

Based on and subject to the foregoing, we are of the opinion that the Shares have been duly authorized by the Company and, when the Shares are issued and paid for by the Plan participants as contemplated by the Plans and in accordance with the terms and conditions of the Plans and the applicable award agreements, the Shares will be validly issued, fully paid and non-assessable.

HealthSouth Corporation

March 30, 2007

Page 3

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Skadden, Arps, Slate, Meagher & Flom LLP