Encompass Health 8K Entry into a Material Definitive Agreement | EHC 12 Mar 15

Exhibit 5.1

[Covington & Burling LLP Letterhead]

March 12, 2015

HealthSouth Corporation

3660 Grandview Parkway, Suite 200

Birmingham, Alabama 35243

Ladies and Gentlemen:

We have acted as counsel to HealthSouth Corporation, a Delaware corporation (the “Company”), in connection with the registration by the Company under the Securities Act of 1933 (the “Act”) of (i) $300,000,000 in aggregate principal amount of the Company’s 5.125% Notes due 2023 (the “Notes”), and (ii) Guarantees of the Notes (the “Guarantees”) by certain subsidiaries of the Company listed in Part I of Appendix A hereto (collectively the “Guarantors”), in each case issued pursuant to the Indenture, dated December 1, 2009 (the “Base Indenture”), as supplemented by a Fifth Supplemental Indenture thereto relating to the Notes, dated as of March 12, 2015 (the “Fifth Supplemental Indenture,” and, together with the Base Indenture, the “Indenture”), between the Company, the Guarantors, and Wells Fargo Bank, National Association, as successor to the Bank of Nova Scotia Trust Company of New York, as trustee (the “Trustee”), pursuant to the registration statement on Form S-3 (File No. 333-183740), filed with the Securities and Exchange Commission (the “Commission”) on September 6, 2012 (such registration statement, as amended to the date hereof, is herein referred to as the “Registration Statement”).

We have reviewed such corporate records, certificates and other documents, and such questions of law, as we have considered necessary or appropriate for the purposes of this opinion. We have assumed that all signatures are genuine, that all documents submitted to us as originals are authentic and that all copies of documents submitted to us conform to the originals.

We have assumed further that the Trustee has duly authorized, executed and delivered the Indenture. We have assumed further that (i) each of the Guarantors listed in Part II of Appendix A hereto (collectively the “Non-Delaware Guarantors”) is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization and has all requisite power, authority and legal right to execute, deliver and perform its obligations under the Indenture and each Guarantee to which it is a party, as applicable, and (ii) each Non-Delaware Guarantor has duly authorized, executed and delivered the Indenture and each Guarantee to which it is a party.

We have relied as to certain matters on information obtained from public officials, officers of the Company and the Guarantors, and other sources believed by us to be responsible.

Based upon the foregoing, and subject to the qualifications set forth below, we are of the opinion that when (i) the Registration Statement and any required post-effective amendments thereto have all become effective under the Act, (ii) the Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, and (iii) the Notes and the Guarantees have been duly executed by the Company and the Guarantors, respectively, and authenticated by the Trustee in accordance with the Indenture and have been duly issued and delivered against payment therefor as contemplated in the Registration Statement, the Notes and the Guarantees will constitute the valid and binding obligations of the Company and the

Guarantors, respectively, enforceable against the Company and the Guarantors, respectively, in accordance with their terms, subject to bankruptcy, insolvency, fraudulent transfer, reorganization, moratorium and other laws of general applicability relating to or affecting creditors’ rights and to general equity principles.

The foregoing opinion is subject to the following qualifications. We express no opinion as to: (i) waivers of defenses, subrogation and related rights, rights to trial by jury, rights to object to venue, or other rights or benefits bestowed by operation of law; (ii) indemnification, contribution, or exculpation provisions, or provisions for the non-survival of representations, to the extent they purport to indemnify any party against, or release or limit any party’s liability for, its own breach or failure to comply with statutory obligations, or to the extent such provisions are contrary to public policy; (iii) provisions for liquidated damages and penalties, penalty interest and interest on interest; (iv) provisions purporting to supersede equitable principles, including provisions requiring amendments and waivers to be in writing and provisions making notices effective even if not actually received; or (v) provisions purporting to make a party’s determination conclusive.

We express no opinion as to the existence or adequacy of consideration received by any Guarantor for the Guarantees.

We are members of the bar of the District of Columbia and the State of New York. We do not express any opinion herein on any laws other than the law of the State of New York, the Delaware General Corporation Law, the Delaware Limited Liability Company Act, and the Delaware Revised Uniform Limited Partnership Act and applicable provisions of the Delaware Constitution and reported judicial decisions interpreting these laws, and the federal law of the United States of America.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Company’s Current Report on Form 8-K being filed on the date hereof and incorporated by reference into the Registration Statement. We also hereby consent to the reference to our firm under the heading “Legal Matters” in the prospectus supplement dated March 9, 2015 constituting part of the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission.

Very truly yours,

/s/ Covington & Burling LLP

APPENDIX A

Part I

All Guarantors

Advantage Health, LLC

CMS Jonesboro Rehabilitation, Inc.

CMS Topeka Rehabilitation, Inc.

Continental Medical of Arizona, Inc.

Continental Medical Systems, Inc.

Continental Rehabilitation Hospital of Arizona, Inc.

HealthSouth Arizona Real Estate, LLC

HealthSouth Aviation, LLC

HealthSouth Bakersfield Rehabilitation Hospital, LLC

HealthSouth California Real Estate, LLC

HealthSouth Colorado Real Estate, LLC

HealthSouth Deaconess Holdings, LLC

HealthSouth East Valley Rehabilitation Hospital, LLC

HealthSouth Harmarville Rehabilitation Hospital, LLC

HealthSouth Johnson City Holdings, LLC

HealthSouth Joint Ventures Holdings, LLC

HealthSouth Kansas Real Estate, LLC

HealthSouth Kentucky Real Estate, LLC

HEALTHSOUTH LTAC of Sarasota, Inc.

HealthSouth Littleton Rehabilitation, LLC

HealthSouth Martin County Holdings, LLC

HealthSouth Middletown Rehabilitation Hospital, LLC

HealthSouth Nevada Real Estate, LLC

HealthSouth New Mexico Real Estate, LLC

HealthSouth Northern Kentucky Rehabilitation Hospital, LLC

HEALTHSOUTH of Dothan, Inc.

HealthSouth of East Tennessee, LLC

HealthSouth of Erie, LLC

HealthSouth of Fort Smith, LLC

HEALTHSOUTH of Montgomery, Inc.

HEALTHSOUTH of Nittany Valley, Inc.

HealthSouth of Pittsburgh, LLC

HEALTHSOUTH of South Carolina, Inc.

HEALTHSOUTH of Spring Hill, Inc.

HealthSouth of Toms River, LLC

HEALTHSOUTH of Treasure Coast, Inc.

HealthSouth of York, LLC

HEALTHSOUTH of Yuma, Inc.

A-1

HealthSouth Ohio Real Estate, LLC

HealthSouth Owned Hospitals Holdings, LLC

HealthSouth Pennsylvania Real Estate, LLC

HealthSouth Plano Rehabilitation Hospital, LLC

HealthSouth Properties, LLC

HealthSouth Reading Rehabilitation Hospital, LLC

HealthSouth Real Estate, LLC

HealthSouth Real Property Holding, LLC

HealthSouth Rehabilitation Center of New Hampshire, Inc.

HEALTHSOUTH Rehabilitation Center, Inc.

HealthSouth Rehabilitation Hospital at Drake, LLC

HealthSouth Rehabilitation Hospital of Arlington, LLC

HealthSouth Rehabilitation Hospital of Austin, Inc.

HealthSouth Rehabilitation Hospital of Beaumont, LLC

HealthSouth Rehabilitation Hospital of Charleston, LLC

HealthSouth Rehabilitation Hospital of Cypress, LLC

HealthSouth Rehabilitation Hospital of Desert Canyon, LLC

HealthSouth Rehabilitation Hospital of Fort Worth, LLC

HealthSouth Rehabilitation Hospital of Fredericksburg, LLC

HealthSouth Rehabilitation Hospital of Gadsden, LLC

HealthSouth Rehabilitation Hospital of Henderson, LLC

HealthSouth Rehabilitation Hospital of Humble, LLC

HealthSouth Rehabilitation Hospital of Largo, LLC

HealthSouth Rehabilitation Hospital of Las Vegas, LLC

HEALTHSOUTH Rehabilitation Hospital of Manati, Inc.

HealthSouth Rehabilitation Hospital of Marion County, LLC

HealthSouth Rehabilitation Hospital of Mechanicsburg, LLC

HealthSouth Rehabilitation Hospital of Miami, LLC

HealthSouth Rehabilitation Hospital of Midland/Odessa, LLC

HealthSouth Rehabilitation Hospital of Modesto, LLC

HealthSouth Rehabilitation Hospital of New Mexico, LLC

HealthSouth Rehabilitation Hospital of Newnan, LLC

HealthSouth Rehabilitation Hospital of Northern Virginia, LLC

HealthSouth Rehabilitation Hospital of Petersburg, LLC

HealthSouth Rehabilitation Hospital of San Juan, Inc.

HealthSouth Rehabilitation Hospital of Sarasota, LLC

HealthSouth Rehabilitation Hospital of Seminole County, LLC

HealthSouth Rehabilitation Hospital of Sewickley, LLC

HealthSouth Rehabilitation Hospital of South Jersey, LLC

HealthSouth Rehabilitation Hospital of Sugar Land, LLC

HealthSouth Rehabilitation Hospital of Tallahassee, LLC

HealthSouth Rehabilitation Hospital of Texarkana, Inc.

HealthSouth Rehabilitation Hospital of Utah, LLC

HealthSouth Rehabilitation Hospital The Woodlands, Inc.

HealthSouth Rehabilitation Institute of San Antonio (RIOSA), Inc.

HealthSouth Rehabilitation Institute of Tucson, LLC

A-2

HealthSouth Savannah Holdings, LLC

HealthSouth Scottsdale Rehabilitation Hospital, LLC

HealthSouth Sea Pines Holdings, LLC

HealthSouth South Carolina Real Estate, LLC

HealthSouth Specialty Hospital of North Louisiana, LLC

HealthSouth Sub-Acute Center of Mechanicsburg, LLC

HealthSouth Sunrise Rehabilitation Hospital, LLC

HealthSouth Support Companies, LLC

HealthSouth Texas Real Estate, LLC

HealthSouth Tucson Holdings, LLC

HealthSouth Utah Real Estate, LLC

HealthSouth Valley of the Sun Rehabilitation Hospital, LLC

HealthSouth Virginia Real Estate, LLC

HealthSouth Walton Rehabilitation Hospital, LLC

HealthSouth West Virginia Real Estate, LLC

Lakeshore System Services of Florida, Inc.

Lakeview Rehabilitation Group Partners

New England Rehabilitation Management Co., LLC

Print Promotions Group, LLC

Rebound, LLC

Rehab Concepts Corp.

Rehabilitation Hospital Corporation of America, LLC

Rehabilitation Hospital of Colorado Springs, Inc.

Rehabilitation Hospital of Nevada-Las Vegas, Inc.

Rehabilitation Hospital of Plano, LLC

Rehabilitation Institute of Western Massachusetts, LLC

Sherwood Rehabilitation Hospital, Inc.

Southern Arizona Regional Rehabilitation Hospital, L.P.

Tarrant County Rehabilitation Hospital, Inc.

Tyler Rehabilitation Hospital, Inc.

Western Medical Rehab Associates, L.P.

Western Neuro Care, Inc.

Part II

Non-Delaware Guarantors