Exhibit 3.125

CERTIFICATE OF INCORPORATION

OF

HEALTHSOUTH Real Property Holding Corporation

FIRST: The name of the Corporation is HEALTHSOUTH Real Property Holding Corporation.

SECOND: The Corporation shall have perpetual duration.

THIRD: The address of the Corporation’s registered office in the State of Delaware is 1209 Orange Street, in the City of Wilmington, County of New Castle. The name of its registered agent at such address is The Corporation Trust Company.

FOURTH: The nature of the business or purposes to be conducted or promoted are:

(a) To acquire by purchase, subscription, underwriting, or otherwise, and to own, hold for investment, or otherwise, and to use, sell, assign, transfer, mortgage, create security interests in, pledge, exchange, or otherwise dispose of real and personal property of every sort and description and wheresoever situated, including shares of stock, bonds, debentures, notes, scrip, securities, evidences of indebtedness, contracts, or obligations of any corporations, associations, or trust estates, domestic or foreign, or of any firm or individual or of the United States or any state, territory, or dependency of the United States or any foreign country, or any municipality or local authority within or without the United States, and also to issue in exchange therefor stocks, bonds, or other securities or evidences of indebtedness of this Corporation, and, while the owner or holder of any such property, to receive, collect, and dispose of the interest, dividends, and income on or from such property and to possess and exercise in respect thereto all of the rights, powers, and privileges or ownership, including all voting power thereon.

(b) To engage in any lawful act or activity for which corporations may be organized under the General Corporation Law of the State of Delaware.

FIFTH: The total number of shares of stock which the Corporation shall have authority to issue is 1,000 shares, consisting of 1,000 shares of Common Stock, par value $,01 per share.

SIXTH: The name and mailing address of the sole Incorporator is as follows:

C. Drew Demaray

800 AmSouth-Sonat Towers

1900 Fifth Avenue North

Birmingham, Alabama 35203

1

SEVENTH: The Board of Directors shall have the power to make, alter or repeal the Bylaws of the Corporation at any meeting at which a quorum is present by the affirmative vote of a majority of the whole Board of Directors. Election of Directors need not be by written ballot. The names and mailing addresses of the initial Board of Directors, to serve until their successors are elected and qualified pursuant to the General Corporation Law of the State of Delaware and the Bylaws adopted by this Corporation, are as follows:

Richard M. Scrushy

Two Perimeter Park South

Suite 224W

Birmingham, Alabama 35243

Aaron Beam, Jr.

Two Perimeter Park South

Suite 224W

Birmingham, Alabama 35243

Anthony J. Tanner

Two Perimeter Park South

Suite 224W

Birmingham, Alabama 35243

EIGHTH: A Director of the Corporation shall have no personal liability to the Corporation or its stockholders for monetary damages for breach of fiduciary duty as a Director, provided, however, that this Article EIGHTH shall not eliminate or limit the liability of a Director, except to the extent permitted by applicable law, (i) for any breach of the Director’s duty of loyalty to the Corporation or its stockholders, (ii) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law, (iii) under Section 174 of the General Corporation Law of the State of Delaware as the same now exists or may hereafter be amended, or (iv) for any transaction from which the Director derived an improper personal benefit. No amendment to, or repeal of, this Article EIGHTH shall apply to, or have any effect on, the liability or alleged liability of any Director for, or with respect to, any acts or omissions of such director occurring prior to such amendment or repeal.

The undersigned, being the sole Incorporator hereinbefore named, for the purpose of forming a corporation pursuant to the General Corporation Law of the State of Delaware, does make this Certificate and does hereby declare and certify that the facts stated herein are true, and accordingly does hereunto sign this Certificate of Incorporation this 2nd day of April, 1991.

/s/ C. Drew Demaray

C. Drew Demaray

2